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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* swapNodes(struct ListNode* head, int k) {
10 int length = 0;
11 struct ListNode* first = head;
12 struct ListNode* second = head;
13 struct ListNode* current = head;
14
15 // First pass to compute the length and locate the kth node from the start
16 for (; current != NULL; current = current->next) {
17 length++;
18 if (length == k) {
19 first = current;
20 }
21 }
22
23 // Second pass to locate the kth node from the end
24 current = head;
25 for (int i = 0; i < length - k; i++) {
26 current = current->next;
27 }
28 second = current;
29
30 // Swap the values
31 int temp = first->val;
32 first->val = second->val;
33 second->val = temp;
34
35 return head;
36}
37The above C solution maintains three pointers: first, second, and current. It first iterates through the linked list to determine the node at position k from the start and counts the list to obtain the total length. Then, it calculates the position for the kth node from the end using this length. By traversing again, it locates the kth node from the end. Finally, it swaps the values of these two nodes.
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).
1
This C solution uses two pointers, fast and slow. Initially, fast moves k steps ahead. While it goes till the end, the slow pointer marks the kth position from the end. Thus, after the loop, we hold references to both kth from start and end, allowing us to swap their values.