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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* swapPairs(struct ListNode* head) {
10 struct ListNode dummy;
11 dummy.next = head;
12 struct ListNode* prev = &dummy;
13
14 while (prev->next && prev->next->next) {
15 struct ListNode* a = prev->next;
16 struct ListNode* b = a->next;
17 a->next = b->next;
18 b->next = a;
19 prev->next = b;
20 prev = a;
21 }
22
23 return dummy.next;
24}The solution uses a dummy node to handle edge cases smoothly, such as when the list has less than two nodes. The dummy node is set at the beginning before the head. We iterate through the list while there are at least two nodes to swap.
We store references to the nodes to be swapped (a and b), rearrange the pointers to complete the swap, and finally, move the prev pointer to the current a, setting up for the next iteration.
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
For JavaScript, the function checks if there is not enough remaining length to require a swap. For valid segments, it uses the second node as new head and recursively swaps the rest of the list, incrementally building back with the head exchanging positions during rinse and repeat across the pairs.