Pairwise Swap Adjacent Nodes of a Linked List by Changing Pointers | Set 2

Table of Contents#

1. Understanding the Linked List Structure
2. The Problem Statement
3. The Algorithm
4. Implementation in Python
5. Common Practices and Best Practices
6. Example Usage
7. Complexity Analysis
8. References

Understanding the Linked List Structure#

A linked list consists of nodes. Each node has two parts: a data element and a pointer (reference) to the next node in the list. For example, in Python, a simple node class can be defined as:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

And a linked list class can be:

class LinkedList:
    def __init__(self):
        self.head = None

The Problem Statement#

Given a linked list, swap every two adjacent nodes and return its head. For example, if the linked list is 1 -> 2 -> 3 -> 4, after swapping adjacent nodes pairwise, it should become 2 -> 1 -> 4 -> 3.

The Algorithm#

1. Create a dummy node: This helps in handling the case when the head of the linked list needs to be swapped. Let's call this dummy node prev_head. Set prev_head.next to the original head of the linked list.

2. Initialize pointers: Have three pointers - prev (which will point to the node before the pair to be swapped), curr (which points to the first node of the pair), and next_node (which points to the second node of the pair).

3. Iterate through the list: While curr and curr.next are not None (meaning there is a pair to swap):

   • Update the pointers:
     • next_node = curr.next
     • curr.next = next_node.next
     • next_node.next = curr
     • prev.next = next_node
   • Move the pointers forward:
     • prev = curr
     • curr = curr.next

4. Return the new head: The new head of the linked list is prev_head.next.

Implementation in Python#

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    def pairwise_swap(self):
        prev_head = Node(0)
        prev_head.next = self.head
        prev = prev_head
        curr = self.head
 
        while curr and curr.next:
            next_node = curr.next
            curr.next = next_node.next
            next_node.next = curr
            prev.next = next_node
 
            prev = curr
            curr = curr.next
 
        self.head = prev_head.next
        return self.head
 
    def print_list(self):
        temp = self.head
        while temp:
            print(temp.data, end=" ")
            temp = temp.next
        print()

Common Practices and Best Practices#

• Error handling: In a more robust implementation, add checks for an empty linked list (i.e., when self.head is None). For example, at the beginning of the pairwise_swap method, you can add:

if not self.head:
    return self.head

• Memory management: In languages like C or C++, make sure to handle memory deallocation properly. In Python, the garbage collector takes care of it to some extent, but it's good to be aware.
• Code readability: Use descriptive variable names as shown in the code above (prev_head, prev, curr, next_node). This makes the code easier to understand and maintain.

Example Usage#

# Create a linked list: 1 -> 2 -> 3 -> 4
llist = LinkedList()
llist.head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
 
llist.head.next = second
second.next = third
third.next = fourth
 
print("Original list:")
llist.print_list()
 
llist.pairwise_swap()
 
print("List after pairwise swap:")
llist.print_list()

Complexity Analysis#

• Time complexity: The algorithm iterates through the linked list once. So, the time complexity is $O(n)$, where $n$ is the number of nodes in the linked list.
• Space complexity: We are using a constant amount of extra space (the prev_head node and a few pointers). So, the space complexity is $O(1)$.

References#

• CLRS (Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein) for general data structure and algorithm concepts.
• Online coding platforms like LeetCode (where similar linked list problems are available for practice) - LeetCode - Swap Nodes in Pairs

This approach provides an efficient way to swap adjacent nodes in a linked list. By following the steps and best practices outlined, you can implement this operation in your own codebase with confidence.