Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        while prev.next and prev.next.next:
            first = prev.next
            second = first.next

            # Swapping
            prev.next = second
            first.next = second.next
            second.next = first

            # Move prev two nodes ahead
            prev = first
        return dummy.next
      

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        while (prev->next && prev->next->next) {
            ListNode* first = prev->next;
            ListNode* second = first->next;

            // Swapping
            prev->next = second;
            first->next = second->next;
            second->next = first;

            // Move prev two nodes ahead
            prev = first;
        }
        return dummy.next;
    }
};
      

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = first.next;

            // Swapping
            prev.next = second;
            first.next = second.next;
            second.next = first;

            // Move prev two nodes ahead
            prev = first;
        }
        return dummy.next;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    while (prev.next !== null && prev.next.next !== null) {
        let first = prev.next;
        let second = first.next;

        // Swapping
        prev.next = second;
        first.next = second.next;
        second.next = first;

        // Move prev two nodes ahead
        prev = first;
    }
    return dummy.next;
};
      

Problem Description

Given the head of a singly linked list, swap every two adjacent nodes and return its head. You must solve the problem by modifying the nodes themselves (i.e., only changing the next pointers), not by swapping the values inside the nodes.

• Each node in the list contains an integer value and a reference to the next node.
• You must not create new nodes for the existing data, but you can use extra pointers for manipulation.
• There is only one valid solution for each input list.
• Do not reuse or duplicate nodes; only rearrange their next pointers.
• If the list has an odd number of nodes, the last node remains in its original position.

Thought Process

When first approaching this problem, you might think about swapping the values of each pair of nodes. However, the problem specifically requires swapping the nodes themselves by changing their next pointers, not their values.

A brute-force approach could involve copying values or reconstructing the list, but this is not allowed. Instead, we need to carefully manipulate pointers so that every two adjacent nodes are swapped. This means for every pair, the first node should point to the node after the second, and the second node should point to the first.

The challenge is to handle the edge cases, such as lists with an odd number of nodes or empty lists, and to keep track of the nodes before and after each pair to maintain the overall structure of the list.

Solution Approach

We can solve this problem by iteratively traversing the linked list and swapping nodes in pairs. Here is a step-by-step breakdown:

1. Introduce a Dummy Node: Create a new node called dummy and set its next pointer to the head of the list. This simplifies edge cases, especially when swapping the first pair.
2. Use a Pointer for Traversal: Use a pointer (prev) that always points to the node before the current pair being swapped.
3. Swap in Pairs: While there are at least two nodes ahead (prev.next and prev.next.next are not null), do the following:
   • Let first be prev.next and second be first.next.
   • Point prev.next to second.
   • Point first.next to second.next.
   • Point second.next to first.
4. Move Forward: After swapping, move prev forward to first (which is now the second node in the swapped pair).
5. Return the New Head: After all swaps, return dummy.next, which now points to the new head of the list.

This approach avoids recursion and extra space, and the dummy node ensures that even the head can be swapped without special handling.

Example Walkthrough

Let's walk through an example with input list: 1 -> 2 -> 3 -> 4

1. Initial State: dummy -> 1 -> 2 -> 3 -> 4
2. First Swap:
   • first = 1, second = 2
   • Update pointers:
     • dummy.next = 2
     • 1.next = 3
     • 2.next = 1
   • List now: dummy -> 2 -> 1 -> 3 -> 4
3. Second Swap:
   • prev = 1, first = 3, second = 4
   • Update pointers:
     • 1.next = 4
     • 3.next = null
     • 4.next = 3
   • List now: dummy -> 2 -> 1 -> 4 -> 3
4. End of List: No more pairs to swap. Return dummy.next which is 2.

Final output: 2 -> 1 -> 4 -> 3

Time and Space Complexity

• Brute-force Approach: If you were to copy values or create new nodes, the time complexity would still be O(n), but the space complexity could be O(n) due to extra nodes or arrays.
• Optimized Approach (Pointer Manipulation):
  • Time Complexity: O(n), because each node is visited and manipulated at most once.
  • Space Complexity: O(1), since only a constant number of pointers are used, regardless of the list size.

The optimized approach is both time-efficient and space-efficient, making it ideal for large linked lists.

Summary

To solve the "Swap Nodes in Pairs" problem, we avoid value swapping and instead manipulate node pointers directly. By using a dummy node and iteratively updating next pointers for each pair, we ensure a clean and efficient solution. The approach is elegant because it handles all edge cases (including the head swap and odd-length lists) without recursion or extra space, and runs in linear time with constant space.