Table of contents
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]
Example 2:
Input: head = []
Output: []
Example 3:
Input: head = [1]
Output: [1]
Constraints:
The number of nodes in the list is in the range
[0, 100].0 <= Node.val <= 100
Iterative Approach
To iterate through a linked list, it's pretty straightforward. We create a dummy head, point curr to the dummy head, and iterate through the list by moving curr to the next.
One of the hardest part is to understand the edge cases and ensuring the loop terminates correctly. One way I've found to make this easier is to use a visual method.
Let's create a linked list:
1 => 2 => 3 => 4 => 5
The task is to swap every two nodes: 2 => 1 => 4 => 3 => 5
Obviously when the number of the given linked list is odd, there will be one left at the tail, while if the number is even, there will be nothing left. This helps us understand the termination of the loop: curr.next is null or curr.next.next is null.
To swap 1 => 2 for example, if we initialise curr to be the head, which is 1 in this case, we couldn't find the pointer to the head. Therefore a dummy head is needed.
When curr is pointing to the dummy head, if we point 2 to 1 directly, obvisouly, we lost the pointer to 2 again, so we need to store the reference to 2 in a temp1 node to prevent this from happening.
dummyHead(curr)=> 2 => 1
After swap, we need to point 1 to 3, but again because we already pointed 2 to 1 now, we lost the pointer to 3. To prevent this, we need temp2 to store 3
dummyHead(curr)=> 2 => 1 => 3 => 4 ...
The next step is to move curr to the next next pointer which is 1. Because each time before we swap, curr needs to be one node before the swap point.
dummyHead=> 2 => 1 (curr) =>3 => 4 ...
After completing the iteration and performing all swaps, return dummy_head.next, which points to the head of the modified linked list.
Solution
/**
* 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 dummyHead = new ListNode(0, head);
let curr = dummyHead
while (curr.next && curr.next.next) {
let temp1 = curr.next
let temp2 = curr.next.next.next
curr.next = curr.next.next
curr.next.next = temp1
temp1.next = temp2
curr = curr.next.next
}
return dummyHead.next
}
Conclusion
By using a temporary variable to hold the reference to the next pair of nodes, you ensure that you don't lose track of any nodes during the swapping process. This step is crucial for correctly manipulating the pointers in the linked list.