Swap Nodes in Pairs
MedPrompt
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Explanation:
Example 2:
Input: head = []
Output: []
Example 3:
Input: head = [1]
Output: [1]
Example 4:
Input: head = [1,2,3]
Output: [2,1,3]
Constraints:
- The number of nodes in the list is in the range
[0, 100]. 0 <= Node.val <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach solves the problem by defining a function that swaps the first two nodes of a list and then recursively calls itself on the rest of the list. The base case for the recursion is a list with zero or one node, which is returned as is.
Algorithm
- Check for the base case: if the list is empty (
head == null) or has only one node (head.next == null), return theheadas no swap is possible. - Identify the first two nodes to be swapped:
firstNode = headandsecondNode = head.next. - The rest of the list, starting from
secondNode.next, needs to be processed recursively. CallswapPairs(secondNode.next). - Link the
firstNodeto the result of the recursive call. This meansfirstNode.nextwill point to the head of the swapped sublist. - Perform the swap for the current pair:
secondNode.nextshould point tofirstNode. - Return
secondNode, as it is the new head of this swapped pair.
Walkthrough
The recursive solution elegantly mirrors the definition of the problem. The main idea is to handle the first pair of nodes and then delegate the swapping of the remaining pairs to a recursive call.
Let's consider the list 1 -> 2 -> 3 -> 4. The function swapPairs is called on the head (node 1).
- It identifies the first pair (1, 2).
- It knows that after swapping, node 1's
nextpointer should point to the result of swapping the rest of the list, which is3 -> 4. - It makes a recursive call
swapPairs(3). This call will return the head of the swapped sublist, which is4 -> 3. - Now, it can complete the swap of the first pair. It sets
1.nextto4and2.nextto1. - Finally, it returns
2as the new head of the entire list.
/** * Definition for singly-linked list. * public 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) { // Base case: if the list has 0 or 1 node, no swaps needed. if (head == null || head.next == null) { return head; } // Nodes to be swapped ListNode firstNode = head; ListNode secondNode = head.next; // Recursively call for the list starting from the third node. // This will be the new next for the first node after swapping. firstNode.next = swapPairs(secondNode.next); // Swap the first two nodes by changing pointers secondNode.next = firstNode; // secondNode is the new head of the swapped pair return secondNode; }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
The code is concise and closely follows the recursive structure of the problem, which can make it easier to understand.
It naturally handles the head of the list without needing a special dummy node.
Cons
The space complexity is O(N) due to the recursion call stack, which is less efficient than an iterative solution.
For extremely long linked lists, this approach could lead to a
StackOverflowError(though not an issue with the problem's constraints).
This approach iterates through the linked list, swapping nodes in pairs. A dummy node is used to simplify the logic, especially for swapping the first pair of nodes, as it provides a constant reference to the node preceding the pair being swapped.
Algorithm
- Create a
dummynode and set itsnextpointer to theheadof the list. This simplifies handling the list's head. - Initialize a
prevNodepointer to thedummynode. - Iterate through the list as long as the current node and its next node are not null.
- In each iteration, identify the pair to be swapped:
firstNode(current) andsecondNode(current.next). - Rearrange the pointers to perform the swap:
prevNode.nextpoints tosecondNode.firstNode.nextpoints tosecondNode.next.secondNode.nextpoints tofirstNode.
- Update
prevNodetofirstNode(which is now the second node in the swapped pair) to prepare for the next iteration. - Move the current pointer to the start of the next pair.
- After the loop finishes, return
dummy.next, which now points to the new head of the modified list.
Walkthrough
To achieve optimal O(1) space complexity, we can solve the problem iteratively. This avoids the overhead of the recursion stack. The key is to carefully manage the pointers to relink the nodes correctly after each swap.
We use a dummy node that points to the original head. This dummy node's next pointer will eventually point to the new head of the modified list. A prevNode pointer tracks the node just before the pair we are about to swap, allowing us to correctly link the previous part of the list to the newly swapped pair.
For a list 1 -> 2 -> 3 -> 4, the process is:
- Initial state:
dummy -> 1 -> 2 -> 3 -> 4.prevNodeisdummy. - Iteration 1: Swap 1 and 2.
prevNode(dummy) now points to 2. The list becomesdummy -> 2 -> 1 -> 3 -> 4. UpdateprevNodeto 1 for the next swap. - Iteration 2: Swap 3 and 4.
prevNode(node 1) now points to 4. The list becomesdummy -> 2 -> 1 -> 4 -> 3. UpdateprevNodeto 3. - The loop terminates as there are no more pairs.
- The final list is returned by
dummy.next.
/** * Definition for singly-linked list. * public 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) { // A dummy node acts as the previous node for the head. // This simplifies the logic for swapping the first pair. ListNode dummy = new ListNode(0); dummy.next = head; ListNode prevNode = dummy; while (head != null && head.next != null) { // Nodes to be swapped ListNode firstNode = head; ListNode secondNode = head.next; // Swapping prevNode.next = secondNode; firstNode.next = secondNode.next; secondNode.next = firstNode; // Re-initializing the prevNode and head for the next iteration prevNode = firstNode; head = firstNode.next; // a.k.a. the start of the next pair } return dummy.next; }}Complexity
Time
O(N)
Space
O(1)
Trade-offs
Pros
Optimal space complexity of O(1), as it only uses a constant amount of extra space.
Avoids potential stack overflow issues, making it more robust and suitable for very large inputs.
Cons
The pointer manipulation can be slightly more complex to write and debug compared to the recursive version.
Requires a dummy node to handle the edge case of the head gracefully.
Solutions
Solution
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode SwapPairs ( ListNode head ) { if ( head is null || head . next is null ) { return head ; } ListNode t = SwapPairs ( head . next . next ); ListNode p = head . next ; p . next = head ; head . next = t ; return p ; } }/** * Definition for singly-linked list. * public 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 , head ); ListNode pre = dummy ; ListNode cur = head ; while ( cur != null && cur . next != null ) { ListNode t = cur . next ; cur . next = t . next ; t . next = cur ; pre . next = t ; pre = cur ; cur = cur . next ; } 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) { const dummy = new ListNode(0, head); let [pre, cur] = [dummy, head]; while (cur && cur.next) { const t = cur.next; cur.next = t.next; t.next = cur; pre.next = t; [pre, cur] = [cur, cur.next]; } 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 = new ListNode ( 0 , head ); ListNode * pre = dummy ; ListNode * cur = head ; while ( cur && cur -> next ) { ListNode * t = cur -> next ; cur -> next = t -> next ; t -> next = cur ; pre -> next = t ; pre = cur ; cur = cur -> next ; } return dummy -> next ; } };# 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 : Optional [ ListNode ]) -> Optional [ ListNode ]: dummy = ListNode ( next = 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 . nextVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.