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.
1class 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 return dummy.next;
16 }
17}In this Java implementation, a dummy node is used at the start of the list to handle boundary conditions easily. The prev pointer helps traverse the list, allowing us to manage the nodes that need swapping. By adjusting pointers for a and b inside the loop, the pairs are swapped efficiently.
The use of a dummy node makes managing head swaps straightforward, while the iterative approach guarantees traversal of the list in linear time.
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 public ListNode SwapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = head.next;
head.next = SwapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}The recursive swap function in C# returns early if the list segment is too short (<2 nodes). newHead is set to the second in the current pair, and a recursive call flips nodes further down the list. C#'s recursive processing closes out when each base case is reached, enabling easy return traversal building (from the end of the list towards the start).