Sponsored
Sponsored
This approach uses iteration to systematically swap each pair of adjacent nodes in the linked list. The main idea is to traverse the list while keeping track of pointers to the nodes before and after the pair being swapped. By adjusting these pointers, we effectively swap nodes without modifying their values.
Time Complexity: O(n), where n is the number of nodes in the linked list. We process each node once.
Space Complexity: O(1), We are using constant extra space.
1var swapPairs = function(head) {
2 let dummy = new ListNode(0);
3 dummy.next = head;
4 let prev = dummy;
5
6 while (prev.next !== null && prev.next.next !== null) {
7 let a = prev.next;
8 let b = a.next;
9 a.next = b.next;
10 b.next = a;
11 prev.next = b;
12 prev = a;
13 }
14
15 return dummy.next;
16};The JavaScript implementation follows the same pattern by using a dummy node for simplified pointer/structure manipulation to swap pairs of nodes. We readjust pointers within the loop, handling swap in pairs of nodes and ensuring each step maintains proper linkage.
This code ensures that, even when the number of nodes is odd, the remaining node (if any) is left in place without a pair to swap with.
This approach leverages recursion to swap every two adjacent nodes. The key idea is to break the problem into subproblems where you solve for a pair and recursively call to solve for the next. The recursion naturally handles the base case where less than two nodes remain to be swapped.
Time Complexity: O(n), every node is processed once.
Space Complexity: O(n), the call stack in recursive functions uses space proportional to the number of elements.
1
The C implementation uses recursion to address each swap operation. The function swaps the first two nodes and then invokes itself on the remaining list. It continues until it reaches a list with zero or one node, at which point it returns the node itself. This effectively builds the solution from back to front on the call stack, as the reversed remaining pairs are linked to complete the swaps.