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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val=0, ListNode next=null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode SwapNodes(ListNode head, int k) {
12 int length = 0;
13 ListNode first = head, second = head, current = head;
14
15 while (current != null) {
16 length++;
17 if (length == k) {
18 first = current;
19 }
20 current = current.next;
21 }
22
23 current = head;
24 for (int i = 0; i < length - k; i++) {
25 current = current.next;
26 }
27 second = current;
28
29 int temp = first.val;
30 first.val = second.val;
31 second.val = temp;
32
33 return head;
34 }
35}
36In the C# solution, we define a structured approach where the list is processed in two passes. We use count tracking to identify nodes, and swapping is done using a temporary variable. The functionality adheres to the same logic detailed in the multi-pass approach.
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).
This Python solution succinctly utilizes the fast and slow pointer technique where fast traverses k steps initially and subsequently the full length thereafter, allowing the slow pointer to point accurately to the desired kth node from the end. The swapping is directly implemented using Python's native value assignment.