Sponsored
Sponsored
This approach involves two passes through the linked list. In the first pass, we determine the kth node from the beginning. In the second pass, we find the kth node from the end. Once we have both nodes, we swap their values. This approach requires a complete traversal of the list during each pass, but is simple to implement.
Time Complexity: O(n) due to two linear passes through the list. Space Complexity: O(1) since we use only pointers.
1function ListNode(val, next) {
2 this.val = (val === undefined ? 0 : val)
3 this.next = (next === undefined ? null : next)
4}
5
6var swapNodes = function(head, k) {
7 let length = 0;
8 let first = head, second = head, current = head;
9
10 while (current !== null) {
11 length++;
12 if (length === k) {
13 first = current;
14 }
15 current = current.next;
16 }
17
18 current = head;
19 for (let i = 0; i < length - k; i++) {
20 current = current.next;
21 }
22 second = current;
23
24 [first.val, second.val] = [second.val, first.val];
25
26 return head;
27};
28In JavaScript, we similarly define ListNode using constructor syntax. We implement the two-pass method: one loop tracks when we hit the k-th node from beginning and another from end using the tracked length. Finally, we perform a value swap using destructuring syntax.
This approach optimizes the two-pass technique by using a single traversal with two pointers method. The idea is to leverage two pointers where one pointer reaches the kth node while the other starts marking the start from the head. Once the first pointer reaches the end, the second pointer will be at the correct kth position from the end. We then swap the values directly.
Time Complexity: O(n), as we make only one pass of the list. Space Complexity: O(1).
The Java implementation similarly utilizes two pointer techniques where the fast pointer is initially positioned k steps forward, leaving the slow pointer stationary to mark the kth node from the end, which is required for value swapping with the node acquired by fast.