Swapping Nodes in a Linked List - Solution & Explanation
Problem Statement
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:
- The number of nodes in the list is
n. 1 <= k <= n <= 1050 <= Node.val <= 100
Approach Overview
Problem Overview: Given the head of a singly linked list and an integer k, swap the values of the kth node from the beginning and the kth node from the end. The list structure must remain intact, so you typically swap node values rather than rearranging node pointers.
Approach 1: Two Pass Technique (O(n) time, O(1) space)
This method first computes the total length of the linked list. Once you know the length n, the node to swap from the end becomes the (n - k + 1)th node from the beginning. Perform one traversal to count nodes, then a second traversal to locate both the kth node and the (n - k + 1)th node. After locating them, swap their values. The logic is simple and easy to reason about during interviews because you separate the tasks: measure the list, then locate the targets. Time complexity is O(n) due to two linear passes, while space complexity stays O(1) since only a few pointers are used.
Approach 2: Single Pass with Two Pointers (O(n) time, O(1) space)
This optimized approach finds both nodes in a single traversal using the two pointers technique. First iterate until you reach the kth node from the start and keep a reference to it. Then start a second pointer from the head while continuing the traversal with the current pointer until the end. When the first pointer reaches the last node, the second pointer will land exactly on the kth node from the end. Swap the values of these two nodes. This technique works because the gap between the pointers remains constant after the kth node is identified. It completes the entire operation in one pass with O(n) time and O(1) space.
Recommended for interviews: The single-pass two pointer method is usually the expected optimal solution. It demonstrates control over pointer movement and efficient traversal of a linked list. The two-pass method is still valuable because it shows a clear understanding of indexing in linked structures and often serves as the stepping stone toward the optimized approach.
Approach 1: Approach 1: Two Pass Technique
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.
The 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.
Complexity
Time Complexity: O(n) due to two linear passes through the list. Space Complexity: O(1) since we use only pointers.
Approach 2: Approach 2: Single Pass with Two Pointers
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.
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.
Complexity
Time Complexity: O(n), as we make only one pass of the list. Space Complexity: O(1).
Approach 3: Two Pointers
We can first use a fast pointer fast to find the kth node of the linked list, and use a pointer p to point to it. Then, we use a slow pointer slow to start from the head node of the linked list, and move both pointers forward at the same time. When the fast pointer reaches the last node of the linked list, the slow pointer slow points to the kth node from the end of the linked list, and we use a pointer q to point to it. At this point, we only need to swap the values of p and q.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two Pass Technique | Time Complexity: O(n) due to two linear passes through the list. Space Complexity: O(1) since we use only pointers. |
| Approach 2: Single Pass with Two Pointers | Time Complexity: O(n), as we make only one pass of the list. Space Complexity: O(1). |
| Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pass Technique | O(n) | O(1) | When you prefer simpler logic by first computing the list length before locating nodes. |
| Single Pass with Two Pointers | O(n) | O(1) | Best for interviews and optimal implementations where both nodes are found during a single traversal. |
Video Solution
Swapping Nodes in a Linked List - Leetcode 1721 - Python • NeetCodeIO • 17,732 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Swapping Nodes in a Linked List easy or hard?
Swapping Nodes in a Linked List Python/Java solution
How to solve Swapping Nodes in a Linked List in O(n)?
What is the best approach for Swapping Nodes in a Linked List?
Is Swapping Nodes in a Linked List asked at Google/Amazon/Meta?
What data structure is used in Swapping Nodes in a Linked List?
What is the time complexity of Swapping Nodes in a Linked List?
Ready to solve this problem?
Practice Swapping Nodes in a Linked List with our built-in code editor and test cases.
Practice on FleetCode