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.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def swapNodes(self, head: ListNode, k: int) -> ListNode:
8 length = 0
9 first = head
10 second = head
11 current = head
12
13 while current:
14 length += 1
15 if length == k:
16 first = current
17 current = current.next
18
19 current = head
20 for i in range(length - k):
21 current = current.next
22 second = current
23
24 first.val, second.val = second.val, first.val
25
26 return head
27In Python, we create a ListNode class to define nodes of the list. We use a similar technique by traversing through the linked list twice. In the first pass, we ascertain the kth node from the start and the length of the list. In the second pass, we find the kth node from the end, and then swap values.
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).
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode SwapNodes(ListNode head, int k) {
ListNode fast = head, slow = head, first = head;
for (int i = 1; i < k; i++) {
fast = fast.next;
}
first = fast;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
int temp = first.val;
first.val = slow.val;
slow.val = temp;
return head;
}
}
In this C# solution, two pointers acceleration involves fast advancing initially by k, and slow keeping pace until fast refers to end node allocating the correct node for swapping attached by values once both pointers have identified k-th start/end.