You are given the head of a linked list, and an integer k.
Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [1,4,3,2,5]
Example 2:
Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5 Output: [7,9,6,6,8,7,3,0,9,5]
Constraints:
n.1 <= k <= n <= 1050 <= Node.val <= 100In #1721 Swapping Nodes in a Linked List, the goal is to swap the value of the k-th node from the beginning with the k-th node from the end. A common and efficient strategy uses the two‑pointer technique. First, traverse the list to locate the k-th node from the start. Then, continue traversing with another pointer so that when the first pointer reaches the end, the second pointer points to the k-th node from the end.
Instead of restructuring the linked list, many optimal implementations simply swap the node values, which avoids complex pointer manipulation. This keeps the algorithm straightforward while maintaining linear performance.
The approach typically requires only a single pass after identifying the first target node, making it highly efficient for large lists. With careful pointer movement and constant extra memory, the algorithm achieves excellent performance characteristics suitable for coding interviews.
Time Complexity: O(n) because the list is traversed at most once or twice.
Space Complexity: O(1) since no additional data structures are required.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers (swap node values) | O(n) | O(1) |
| Two Pass Traversal (find length then nodes) | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
We can traverse the linked list and store the elements in an array.
Upon conversion to an array, we can swap the required elements by indexing the array.
We can rebuild the linked list using the order of the elements in the array.
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 <iostream>
2
3struct ListNode {
4 int val;
5 ListNode* next;
6 ListNode(int x) : val(x), next(nullptr) {}
7};
8
9ListNode* swapNodes(ListNode* head, int k) {
10 int length = 0;
11 ListNode* first = head;
12 ListNode* second = head;
13 ListNode* current = head;
14
for (; current != nullptr; current = current->next) {
length++;
if (length == k) {
first = current;
}
}
current = head;
for (int i = 0; i < length - k; i++) {
current = current->next;
}
second = current;
std::swap(first->val, second->val);
return head;
}
The C++ solution also follows a similar idea as the C example. We calculate the length of the list and find the k-th nodes from the beginning and the end, then swap their values using std::swap().
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).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, linked list manipulation problems like this frequently appear in FAANG-style interviews. They test understanding of pointer movement, traversal strategies, and space‑efficient problem solving.
A singly linked list is the primary data structure used in this problem. The solution relies on pointer traversal rather than additional data structures, which allows the algorithm to run in constant extra space.
The two-pointer technique allows you to track positions relative to the start and end of the list without computing the length repeatedly. It helps solve problems in a single pass and is widely used for tasks like finding middle nodes, cycles, or relative positions.
The optimal approach uses the two-pointer technique. First locate the kth node from the beginning, then use another pointer to identify the kth node from the end while traversing the list. Swapping their values avoids complex pointer restructuring and keeps the solution efficient.
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.