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.

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

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.