Solution Explanation for Swapping Nodes in Pairs

This problem involves manipulating a linked list to swap adjacent node pairs. We'll explore two approaches: recursion and iteration.

1. Recursive Approach

This approach elegantly solves the problem by recursively swapping pairs from the tail of the list.

• Base Case: If the list is empty or contains only one node, no swapping is needed, so the head is returned.

• Recursive Step:

  1. Recursively swap the pairs starting from head.next.next. This gives us the swapped tail of the list, assigned to t.
  2. Let p point to head.next (the second node).
  3. Swap head and p: p.next = head and head.next = t.
  4. Return p, the new head of the swapped pair.

Code (Python):

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        t = self.swapPairs(head.next.next)
        p = head.next
        p.next = head
        head.next = t
        return p

Time Complexity: O(N), where N is the number of nodes. Each node is visited once.

Space Complexity: O(N) in the worst case due to the recursive call stack. The depth of the recursion is proportional to the length of the list.

2. Iterative Approach

This approach is more efficient in terms of space complexity.

• Initialization: A dummy node is created to simplify handling the head of the list. Pointers pre (previous node) and cur (current node) are initialized.

• Iteration: The while loop continues as long as there are at least two nodes remaining to swap.

  1. t stores a temporary reference to cur.next.
  2. The links are rearranged: cur.next = t.next, t.next = cur, pre.next = t.
  3. pre and cur are updated to move to the next pair.

• Return Value: The dummy.next points to the new head of the list.

Code (Python):

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy = ListNode(0, head)
        pre, cur = dummy, head
        while cur and cur.next:
            t = cur.next
            cur.next = t.next
            t.next = cur
            pre.next = t
            pre, cur = cur, cur.next
        return dummy.next
 

Time Complexity: O(N), as each node is visited once.

Space Complexity: O(1), as only a few constant extra variables are used.

Comparison:

| Feature | Recursive Approach | Iterative Approach | |---------------|----------------------|----------------------| | Time Complexity | O(N) | O(N) | | Space Complexity| O(N) | O(1) | | Readability | More concise | More verbose |

The iterative approach is generally preferred due to its better space complexity. The recursive solution is elegant but can suffer from stack overflow errors for very large linked lists. Both solutions have the same time complexity.