24. Swap Nodes in Pairs


Problem Description

Given a singly linked list, the objective is to swap every two adjacent nodes and return the modified linked list. Unlike simple value swapping, this task requires changing the actual node connections. Importantly, the modification must be carried out without altering the values within the nodes -- in essence, only the node linkages can be reshuffled. The problem also asks for the function to accommodate linked lists with an odd number of nodes, in which case the final node remains in its original position since there's no pair to swap with.

Intuition

Transforming the structure of a linked list often points towards manipulating node pointers. To swap nodes in pairs, we can employ two main strategies: recursion or iteration.

  • Recursive Approach: We perform a depth-first traversal, recursively swapping pairs of nodes. In each recursive call, we handle a pair and then delve deeper, assuming that the rest of the list beyond this pair will be solved in the same recursive manner. When the recursion unwinds, the entire list is thus reordered in pairs.

  • Iterative Approach: Iteration is the alternative strategy that seems natural for this problem, as linked list manipulation often involves loop constructs. The provided code snippet uses an iterative approach with two pointers, which sidesteps the complexities that can come with recursion, such as stack space concerns. We introduce a dummy node that precedes the head of the list for simplicity, allowing us to standardize the swapping process without special-casing the head of the list. Two pointers pre and cur are established to maintain references to the nodes being operated on. cur points at the current node under consideration and pre trails behind, enabling us to properly link the swapped pairs to the rest of the list. By looping through the list and updating these pointers step-by-step, we systematically exchange the adjacent nodes, while preserving the original node values and ensuring all connections are accurately reestablished post-swap.

Learn more about Recursion and Linked List patterns.

Solution Approach

This problem can be resolved by two approaches, recursion or iteration, using the fundamental concepts of linked list traversal and pointer manipulation.

Solution 1: Recursion

The recursive approach to the problem often provides a clean and intuitive solution. Here, we swap each pair of nodes and recursively call the function on the sublist starting with the third node. Here's how the process works:

  1. The base condition checks if the current node (head) is null or if it's the last node with no pair to swap (head.next is null). In either case, the head is returned as-is, since no more swapping is possible.
  2. For any node with at least one adjacent node to swap, we store the next node in t and perform the swap by setting head.next to the recursive call on head.next.next. This effectively links the current head to the result of swapping the rest of the list.
  3. The second node of the pair (t) now needs to point to the first (head), forming the swapped pair, and t is returned as the new head of this swapped section.

Each step handles two nodes and links the swapped pair to the result of the rest of the list, which is computed recursively.

The time complexity of this approach is "O(n)", where "n" is the number of nodes in the linked list, as each node pair is visited once. The space complexity is also "O(n)" on account of the recursive call stack.

Solution 2: Iteration

The iterative solution approach is generally more space-efficient for linked lists as it avoids the overhead of the recursive call stack.

  1. We start by creating a dummy node that acts as a placeholder prior to the head of the list. This allows us to handle the head of the list the same as any other node in the swapping process, which simplifies the code.
  2. We then set two pointers, pre starting at the dummy node, and cur starting at the list's actual head.
  3. Within a loop, as long as cur and its next node cur.next are not null, we perform the swap. We first store the next node in t, then link cur.next to t.next.
  4. After that, t.next is updated to point to cur, effectively placing t before cur.
  5. We now reset the pointer pre.next to t to connect the previous part of the list to our newly swapped pair.
  6. Finally, we update pre to cur (the first node of the swapped pair) and move cur to cur.next to process the next pair.

With this pattern, we successively swap adjacent nodes and move forward in the list until all pairs are swapped or we reach the end of the list.

The time complexity for this iterative approach is also "O(n)" since each node is visited exactly once, while the space complexity is improved to "O(1)" because we aren't making any recursive calls, just reassigning pointers.

Both approaches effectively change node pointers to swap adjacent nodes in pairs without altering the node values, successfully solving the problem at hand.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume we have a linked list with the following values:

[1 -> 2 -> 3 -> 4 -> 5]

Our goal is to swap every pair of adjacent nodes. We'll walk through the iterative approach since it's mentioned in the content provided.

  1. We introduce a dummy node to simplify our process. The list now starts with a dummy node followed by the original nodes:

    [dummy -> 1 -> 2 -> 3 -> 4 -> 5]

    Here, dummy is a standalone node that we use as a starting point, pre starts as the dummy node, and cur starts at the head of the real list (node with value 1).

  2. We check if cur and cur.next (nodes 1 and 2) are not null, to proceed with the swap. Since they are both not null, we move onto swapping the nodes. Let's denote t as the node after cur, which is node 2.

  3. We swap the nodes by reassigning pointers:

    • First, we make cur.next point to t.next (which is node 3):

      [dummy -> 1 ---
      3 -> 4 -> 5] [2 ---/

    • Then we update t.next to point to cur, placing t before cur:

      [dummy ---
      2 -> 1 ---
      3 -> 4 -> 5]

  4. Now we link the previous part of the list (the dummy node) to our swapped pair by setting pre.next to t:

    [dummy -> 2 -> 1 -> 3 -> 4 -> 5]

  5. We then advance our pointers: pre moves to cur (node 1), and cur moves to cur.next (node 3).

  6. We continue with the loop, checking if there are more pairs to swap. Again, cur and cur.next are not null, so we store the node after cur (t, which is node 4) and perform a similar set of pointer reassignments:

    [dummy -> 2 -> 1 ---
    4 -> 3 ---
    5] [3 ---/

    After swapping, we reconnect the list:

    [dummy -> 2 -> 1 -> 4 -> 3 -> 5]

  7. We update pre to cur (node 3) and cur to cur.next (node 5).

  8. Lastly, we find that cur.next is null because node 5 has no pair to swap with. Therefore, we stop the loop and return the head of the modified list, which is the node immediately following our dummy node.

The final swapped list is:

[2 -> 1 -> 4 -> 3 -> 5]

By following these steps iteratively, we've managed to swap the adjacent nodes in pairs throughout the list while maintaining the original values, just as required by the problem statement. The time complexity of this operation is O(n) since we visited each node once, and the space complexity is O(1) due to the constant number of pointers used.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next_node=None):
4        self.val = val
5        self.next = next_node
6
7class Solution:
8    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
9        # Create a dummy node that points to the head of the list
10        dummy = ListNode(next_node=head)
11        prev_node, current_node = dummy, head
12      
13        # Iterate through the list while there are pairs to swap
14        while current_node and current_node.next:
15            # 'temp' is the node that will be swapped with the current node
16            temp = current_node.next
17            # Adjust 'current_node.next' to the node after 'temp'
18            current_node.next = temp.next
19            # The 'temp' node now should point to 'current_node' after swapping
20            temp.next = current_node
21            # 'prev_node.next' is adjusted to point to 'temp' after swapping
22            prev_node.next = temp
23            # Move 'prev_node' and 'current_node' forward in the list
24            prev_node, current_node = current_node, current_node.next
25      
26        # Return the new head of the swapped list
27        return dummy.next
28
1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11class Solution {
12    public ListNode swapPairs(ListNode head) {
13        // The dummy node is used to simplify the edge case where the list might contain only one node.
14        ListNode dummyNode = new ListNode(0);
15        dummyNode.next = head;
16      
17        // 'previousNode' always points to the node before the pair that needs to be swapped.
18        ListNode previousNode = dummyNode;
19        // 'currentNode' is the first node in the pair that needs to be swapped.
20        ListNode currentNode = head;
21      
22        // Iterate over the list in steps of two nodes at a time.
23        while (currentNode != null && currentNode.next != null) {
24            // 'nextNode' is the second node in the pair that needs to be swapped.
25            ListNode nextNode = currentNode.next;
26            // Swap the pair by adjusting the pointers.
27            currentNode.next = nextNode.next;
28            nextNode.next = currentNode;
29            previousNode.next = nextNode;
30          
31            // Move 'previousNode' pointer two nodes ahead to the last node of the swapped pair.
32            previousNode = currentNode;
33            // Advance 'currentNode' to the next pair of nodes to swap.
34            currentNode = currentNode.next;
35        }
36      
37        // The 'next' of dummy node points to the new head after swapping pairs.
38        return dummyNode.next;
39    }
40}
41
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode(int x) : val(x), next(nullptr) {}
7 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
8 *     ListNode() : val(0), next(nullptr) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* swapPairs(ListNode* head) {
14        // Create a dummy node to anchor the modified list and simplify edge cases
15        ListNode* dummyNode = new ListNode(0);
16        dummyNode->next = head;
17
18        // Use 'previousNode' to keep track of the last node of the previous pair
19        ListNode* previousNode = dummyNode;
20
21        // 'currentNode' will be used to iterate through the original list
22        ListNode* currentNode = head;
23
24        // Proceed with swapping pairs while there are at least two nodes left to process
25        while (currentNode && currentNode->next) {
26            // Identify the node to be swapped with the current node
27            ListNode* nextNode = currentNode->next;
28
29            // Swap the pair by reassigning pointers
30            currentNode->next = nextNode->next;
31            nextNode->next = currentNode;
32            previousNode->next = nextNode;
33
34            // Move 'previousNode' pointer forward to the current node after swap
35            previousNode = currentNode;
36
37            // Move 'currentNode' pointer forward to the next pair
38            currentNode = currentNode->next;
39        }
40
41        // The 'dummyNode.next' now points to the head of the modified list
42        ListNode* swappedHead = dummyNode->next;
43
44        // Clean up memory by deleting the dummy node
45        delete dummyNode;
46
47        // Return the head of the modified list with pairs swapped
48        return swappedHead;
49    }
50};
51
1// Type definition for a singly-linked list node.
2type ListNode = {
3    val: number;
4    next: ListNode | null;
5};
6
7// Helper function to create a new ListNode.
8const createListNode = (val: number, next: ListNode | null = null): ListNode => {
9    return { val: val, next: next };
10}
11
12/**
13 * Swaps every two adjacent nodes and returns its head.
14 * Note: This function assumes the existence of a ListNode type.
15 * @param {ListNode | null} head - The head of the linked list.
16 * @return {ListNode | null} - The new head of the modified list.
17 */
18function swapPairs(head: ListNode | null): ListNode | null {
19    // Create a dummy node to simplify edge cases.
20    let dummy = createListNode(0, head);
21  
22    // Initialize pointers for the previous and current nodes.
23    let previous = dummy;
24    let current = head;
25
26    // Traverse the list in pairs.
27    while (current && current.next) {
28        // Store the node following the current node.
29        let temp = current.next;
30        // Skip the next node to point to the one after.
31        current.next = temp.next;
32        // Point the next node back to the current node, effecting the swap.
33        temp.next = current;
34        // Link the previous node to the new head of the swapped pair.
35        previous.next = temp;
36      
37        // Move the pointers forward to the next pair.
38        previous = current;
39        current = current.next;
40    }
41  
42    // Return the new head, which is the next of the dummy node.
43    return dummy.next;
44}
45

Time and Space Complexity

The time complexity of the code is O(n) where n is the number of nodes in the given linked list. This complexity arises because the algorithm must visit each node to swap the pairs, traversing the entire length of the list once.

The space complexity of the code is O(1) because it only uses a constant amount of extra space. The variables dummy, pre, cur, and t are used for manipulation, but the space occupied by these variables does not scale with the size of the input list, thus constituting a constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More