1721. Swapping Nodes in a Linked List - Explanation
Description
Swap the values stored in the kth node from the beginning and the kth node from the end of the linked list, then return its head. Count positions starting at 1 from either end. If both positions refer to the same node, the list is unchanged. Arrays in examples and test inputs list node values from head to tail.
Example 1:
Input: head = [2,4,6,8]
k = 1
Output: [8,4,6,2]Explanation: The first node from the beginning contains 2, and the first from the end contains 8. Swap those values while leaving the two middle values unchanged.
Example 2:
Input: head = [5,1,9,3,7]
k = 2
Output: [5,3,9,1,7]Explanation: The second node from the beginning contains 1, and the second from the end contains 3. Swapping them gives 5 -> 3 -> 9 -> 1 -> 7.
Example 3:
Input: head = [1,2,3]
k = 2
Output: [1,2,3]Explanation: The second node from either end is the same middle node. Swapping its value with itself leaves the list unchanged.
Constraints:
- The list contains
nnodes, where1 <= n <= 100000. 1 <= k <= n0 <= Node.val <= 100
Topics
Prerequisites
Before attempting this problem, you should be comfortable with:
- Linked List Basics - Understanding node structure, traversal, and pointer manipulation
- Two-Pointer Technique - Using multiple pointers to traverse a list simultaneously (for finding the k-th node from the end)
- Recursion - Understanding recursive function calls and how they can track positions from both ends
1. Convert To Array
Intuition
Converting the linked list to an array gives us random access to any position. The k-th node from the beginning is at index k-1, and the k-th node from the end is at index n-k (where n is the length). After swapping values in the array, we simply copy them back to the original nodes. This approach is simple but uses extra space.
Algorithm
- Traverse the linked list and store all values in an array.
- Swap the values at positions
k-1andn-k. - Traverse the linked list again, updating each node's value from the array.
- Return the head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
arr = []
cur = head
while cur:
arr.append(cur.val)
cur = cur.next
n = len(arr)
arr[k - 1], arr[n - k] = arr[n - k], arr[k - 1]
cur, i = head, 0
while cur:
cur.val = arr[i]
cur = cur.next
i += 1
return headTime & Space Complexity
- Time complexity:
- Space complexity:
2. Recursion
Intuition
Recursion naturally gives us access to positions from both ends. As we recurse, we can count from the start (using a variable incremented before the recursive call) to find the k-th node from the beginning. The recursive call returns a count from the end, allowing us to identify the k-th node from the end. Once both nodes are found, we swap their values.
Algorithm
- Use a recursive helper that tracks position from the start via a counter incremented on each call.
- When the start counter equals k, save a reference to the current node as
left. - The recursion returns the position from the end (incrementing on return).
- When the end position equals k, save a reference to the current node as
right. - After recursion completes, swap the values of
leftandright. - Return the head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
left, right, startIdx = None, None, 0
def dfs(node):
nonlocal left, right, startIdx
if not node:
return 0
startIdx += 1
if startIdx == k:
left = node
endIdx = dfs(node.next) + 1
if endIdx == k:
right = node
return endIdx
dfs(head)
if left and right:
left.val, right.val = right.val, left.val
return headTime & Space Complexity
- Time complexity:
- Space complexity: for recursion stack.
3. Iteration (Two Pass)
Intuition
With two passes, we first determine the list length, then locate both target nodes. The k-th node from the beginning is found by advancing k nodes. The k-th node from the end is at position n - k + 1 from the start. In the second pass, we find both positions and swap their values.
Algorithm
- First pass: count the total number of nodes
n. - Second pass: traverse again, keeping track of position.
- When position equals k, save the node as
left. - When position equals
n - k + 1, save the node asright.
- When position equals k, save the node as
- Swap the values of
leftandright. - Return the head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
n = 0
cur = head
while cur:
n += 1
cur = cur.next
left, right = None, None
cur = head
for i in range(1, n + 1):
if i == k:
left = cur
if i == (n - k + 1):
right = cur
cur = cur.next
left.val, right.val = right.val, left.val
return headTime & Space Complexity
- Time complexity:
- Space complexity:
4. Iteration (One Pass) - I
Intuition
We can find both nodes in a single pass using the two-pointer technique. First, advance one pointer k steps to reach the k-th node from the start. Then, start a second pointer from the head and advance both pointers together until the first reaches the end. At that point, the second pointer will be at the k-th node from the end, since it trails by exactly n - k positions.
Algorithm
- Advance a pointer
curexactlyk - 1steps to reach the k-th node. Save it asleft. - Initialize
rightat the head. - Continue advancing
curto the end while also advancingright. - When
cur.nextis null,rightpoints to the k-th node from the end. - Swap the values of
leftandright. - Return the head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
cur = head
for _ in range(k - 1):
cur = cur.next
left = cur
right = head
while cur.next:
cur = cur.next
right = right.next
left.val, right.val = right.val, left.val
return headTime & Space Complexity
- Time complexity:
- Space complexity:
5. Iteration (One Pass) - II
Intuition
This variation uses a slightly different approach: we start right moving only after we have found the k-th node. By decrementing k during traversal, we know exactly when we reach the k-th position. At that moment, we initialize right at the head. From then on, both pointers move together, maintaining their fixed distance until the end.
Algorithm
- Traverse with
cur, decrementing k each step. - When k equals 1, save
curasleftand setrightto head. - Continue traversing. If
rightexists, advance it along withcur. - When
curreaches the end,rightwill be at the k-th node from the end. - Swap the values of
leftandright. - Return the head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
left, right = None, None
cur = head
while cur:
if right:
right = right.next
if k == 1:
left = cur
right = head
k -= 1
cur = cur.next
left.val, right.val = right.val, left.val
return headTime & Space Complexity
- Time complexity:
- Space complexity:
Common Pitfalls
Off-By-One Errors in Position Calculation
The k-th node from the beginning is at position k (1-indexed), requiring k-1 advances from the head. The k-th node from the end is at position n-k+1 from the beginning. Confusing 0-indexed and 1-indexed counting or miscalculating the end position leads to swapping the wrong nodes. Carefully trace through a small example to verify your indexing.
Not Starting the Second Pointer at the Right Time
In the one-pass two-pointer approach, the second pointer (right) must start moving from the head exactly when the first pointer reaches the k-th node. Starting too early or too late means right won't land on the k-th node from the end when the first pointer reaches the list's end. The gap between pointers must be exactly k-1 nodes.
Swapping Nodes Instead of Values
The problem asks to swap the values of two nodes, not the nodes themselves. Swapping node pointers requires updating multiple references (including the previous nodes' next pointers), which is more complex and error-prone. Simply swapping left.val and right.val is cleaner and achieves the same result for this problem.
Sign in to join the discussion