Swap Nodes in Pairs

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We are given a linked list.
  • We need to swap every two adjacent nodes and return the modified linked list.
  • The swapping should be done in-place, and we should not modify the node values, only the node references.

2. Analyze the problem: To solve this problem, we can use a simple iterative approach.

  • We can use three pointers: prev, curr, and next.
  • We'll swap the pairs of nodes by adjusting the node references.
  • We'll keep track of the previous and next nodes to maintain the connectivity of the list.

3. Design an algorithm: Here is the algorithm to solve the problem:

  1. Initialize a dummy node as the head to handle the case when the original head needs to be swapped.
  2. Set prev to the dummy node.
  3. Set curr to the next node of prev.
  4. While both curr and curr.next are not null:
    • Set next to the next node of curr.
    • Set the prev node's next to next.
    • Set curr's next to next.next.
    • Set next's next to curr.
    • Update prev to curr.
    • Update curr to curr.next.
  5. Return the modified linked list by accessing the dummy node's next.

4. Explain your approach: The approach involves using three pointers (prev, curr, and next) to swap the pairs of nodes. We start with a dummy node as the head to handle the case when the original head needs to be swapped. We iterate through the list, adjusting the node references to swap the pairs. By updating the prev, curr, and next pointers accordingly, we can maintain the connectivity of the list.

5. Write clean and readable code:

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def swapPairs(head):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while prev.next and prev.next.next:
        curr = prev.next
        next_node = curr.next

        prev.next = next_node
        curr.next = next_node.next
        next_node.next = curr

        prev = curr
    return dummy.next

6. Test your code: Let's test the code with different test cases to ensure its correctness:

  1. Test case with an empty list:

    • Input: head = None
    • Expected output: None

  2. Test case with a single node:

    • Input: head = ListNode(1)
    • Expected output: ListNode(1)

  3. Test case with an even-sized list:

    • Input: head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
    • Expected output: ListNode(2, ListNode(1, ListNode(4, ListNode(3))))

  4. Test case with an odd-sized list:

    • Input: head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))
    • Expected output: ListNode(2, ListNode(1, ListNode(4, ListNode(3, ListNode(5))))

    The test cases cover scenarios with empty lists, single nodes, even-sized lists, and odd-sized lists to ensure the correctness of the swapping operation.

7. Optimize if necessary: The initial solution already has an optimal time complexity of O(N), where N is the number of nodes in the list. We need to visit each node once to swap the pairs. The space complexity is O(1) since we only use a constant amount of extra space for the pointers.

8. Handle error cases: The code handles the case where the input list is empty. It returns None as the output in that case.

9. Discuss complexity analysis: The time complexity of the solution is O(N), where N is the number of nodes in the list. We need to visit each node once to swap the pairs. The space complexity is O(1) since we only use a constant amount of extra space for the pointers. The solution has an optimal time and space complexity.

Next Post Previous Post