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.
1public class Solution {
2 public ListNode SwapPairs(ListNode head) {
3 ListNode dummy = new ListNode(0);
4 dummy.next = head;
5 ListNode prev = dummy;
6
7 while (prev.next != null && prev.next.next != null) {
8 ListNode a = prev.next;
9 ListNode b = a.next;
10 a.next = b.next;
11 b.next = a;
12 prev.next = b;
13 prev = a;
14 }
15
16 return dummy.next;
17 }
18}In C#, we similarly use a dummy node to simplify swap operations. The prev pointer iterates through the linked list, swapping adjacent nodes by adjusting pointers within the loop. This ensures that each pair is effectively swapped without extra memory usage.
The method returns the next node of the dummy, effectively providing the new head after swaps.
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.
1public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
ListNode* newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}
};This solution applies recursion in C++ by checking the base case for lists with fewer than two nodes. It then performs swaps at the current head and recursively calls to proceed on the rest. newHead will always refer to the second node in the current pair, which becomes the new head upon reversal.
The recursion unfolds by solving subproblems in a LIFO order, ensuring correct linkage on return from each recursive call.