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 pointerspre
andcur
are established to maintain references to the nodes being operated on.cur
points at the current node under consideration andpre
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:
- 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, thehead
is returned as-is, since no more swapping is possible. - For any node with at least one adjacent node to swap, we store the next node in
t
and perform the swap by settinghead.next
to the recursive call onhead.next.next
. This effectively links the currenthead
to the result of swapping the rest of the list. - The second node of the pair (
t
) now needs to point to the first (head
), forming the swapped pair, andt
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.
- 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.
- We then set two pointers,
pre
starting at the dummy node, andcur
starting at the list's actual head. - Within a loop, as long as
cur
and its next nodecur.next
are not null, we perform the swap. We first store the next node int
, then linkcur.next
tot.next
. - After that,
t.next
is updated to point tocur
, effectively placingt
beforecur
. - We now reset the pointer
pre.next
tot
to connect the previous part of the list to our newly swapped pair. - Finally, we update
pre
tocur
(the first node of the swapped pair) and movecur
tocur.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 EvaluatorExample 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.
-
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, andcur
starts at the head of the real list (node with value1
). -
We check if
cur
andcur.next
(nodes1
and2
) are not null, to proceed with the swap. Since they are both not null, we move onto swapping the nodes. Let's denotet
as the node aftercur
, which is node2
. -
We swap the nodes by reassigning pointers:
-
First, we make
cur.next
point tot.next
(which is node3
):[dummy -> 1 ---
3 -> 4 -> 5] [2 ---/ -
Then we update
t.next
to point tocur
, placingt
beforecur
:[dummy ---
2 -> 1 ---
3 -> 4 -> 5]
-
-
Now we link the previous part of the list (the dummy node) to our swapped pair by setting
pre.next
tot
:[dummy -> 2 -> 1 -> 3 -> 4 -> 5]
-
We then advance our pointers:
pre
moves tocur
(node1
), andcur
moves tocur.next
(node3
). -
We continue with the loop, checking if there are more pairs to swap. Again,
cur
andcur.next
are not null, so we store the node aftercur
(t
, which is node4
) 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]
-
We update
pre
tocur
(node3
) andcur
tocur.next
(node5
). -
Lastly, we find that
cur.next
is null because node5
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.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!