Problem Description

You are given the head of a linked list and an integer k.

Your task is to swap the values of two specific nodes in the linked list:

• The kth node from the beginning of the list
• The kth node from the end of the list

The list uses 1-based indexing, meaning the first node is at position 1, the second node is at position 2, and so on.

After swapping the values of these two nodes, return the head of the modified linked list.

For example, if you have a linked list 1 -> 2 -> 3 -> 4 -> 5 and k = 2:

• The 2nd node from the beginning has value 2
• The 2nd node from the end has value 4
• After swapping, the list becomes 1 -> 4 -> 3 -> 2 -> 5

The solution uses a two-pointer technique. First, a fast pointer moves k-1 steps to reach the kth node from the beginning (stored as pointer p). Then, both fast and slow pointers move together until the fast pointer reaches the end. At this point, the slow pointer will be at the kth node from the end (stored as pointer q). Finally, the values at positions p and q are swapped.

Intuition

The key insight is recognizing that finding the kth node from the end is the challenging part, since we can't traverse a singly-linked list backwards. However, we can use the relationship between distances to solve this elegantly.

Think about it this way: if the linked list has n nodes total, then the kth node from the end is actually the (n - k + 1)th node from the beginning. But we don't know n initially, and counting all nodes first would require an extra pass through the list.

Here's where the two-pointer technique becomes clever. If we position one pointer k nodes ahead of another, and then move both pointers together until the leading pointer reaches the end, the trailing pointer will naturally land on the kth node from the end.

Why does this work? When the fast pointer has moved k steps from the start, it has (n - k) more steps to reach the end. If we start a slow pointer from the beginning at this moment and move both pointers together, when the fast pointer completes those (n - k) steps to reach the end, the slow pointer will have moved (n - k) steps from the start, positioning it at the (n - k + 1)th node from the beginning - which is exactly the kth node from the end.

This approach allows us to find both target nodes in a single pass: we mark the kth node from the beginning when our fast pointer reaches it initially, and we find the kth node from the end when our fast pointer reaches the list's end. Then we simply swap the values at these two positions.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

The implementation uses a two-pointer technique to locate both target nodes efficiently in a single pass through the linked list.

Step 1: Find the kth node from the beginning

We initialize two pointers, fast and slow, both pointing to the head of the linked list. We then move the fast pointer forward by k - 1 steps using a loop:

for _ in range(k - 1):
    fast = fast.next

After this loop, fast points to the kth node from the beginning. We store this position in pointer p for later use:

p = fast

Step 2: Find the kth node from the end

Now we need to find the kth node from the end. The trick is to maintain a gap of k nodes between two pointers. Since fast is already k - 1 steps ahead of the head, we can now move both fast and slow pointers together until fast reaches the last node:

while fast.next:
    fast, slow = fast.next, slow.next

When this loop terminates:

• fast.next is None, meaning fast is at the last node
• slow is exactly k nodes behind the end, which makes it the kth node from the end

We store this position in pointer q:

q = slow

Step 3: Swap the values

Instead of manipulating the linked list structure (which would be complex), we simply swap the values of the two nodes:

p.val, q.val = q.val, p.val

Step 4: Return the result

Since we only swapped values and didn't change the structure of the linked list, we return the original head:

return head

The time complexity is O(n) where n is the length of the linked list, as we traverse the list only once. The space complexity is O(1) as we only use a constant number of pointers.

Example Walkthrough

Let's walk through the solution with a concrete example: linked list 1 -> 2 -> 3 -> 4 -> 5 and k = 2.

Initial Setup:

List: 1 -> 2 -> 3 -> 4 -> 5
k = 2 (we want to swap 2nd from beginning with 2nd from end)
fast = head (pointing to 1)
slow = head (pointing to 1)

Step 1: Find the 2nd node from the beginning

Move fast pointer forward by k - 1 = 1 step:

List: 1 -> 2 -> 3 -> 4 -> 5
         fast
slow

After moving, fast points to node with value 2. Store this as p:

p = fast (pointing to node 2)

Step 2: Find the 2nd node from the end

Move both fast and slow together until fast.next is None:

First iteration:

List: 1 -> 2 -> 3 -> 4 -> 5
            slow  fast

Second iteration:

List: 1 -> 2 -> 3 -> 4 -> 5
               slow     fast

Third iteration:

List: 1 -> 2 -> 3 -> 4 -> 5
                  slow     fast

Now fast.next is None (fast is at the last node), so we stop. slow points to node with value 4, which is the 2nd node from the end. Store this as q:

q = slow (pointing to node 4)

Step 3: Swap the values

We have:

• p pointing to node with value 2 (2nd from beginning)
• q pointing to node with value 4 (2nd from end)

Swap their values:

p.val, q.val = q.val, p.val

After swapping:

• Node at position 2 now has value 4
• Node at position 4 now has value 2

Step 4: Return the result

The final linked list is: 1 -> 4 -> 3 -> 2 -> 5

Return the original head pointer, which still points to the first node of the modified list.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the linked list.

The algorithm makes two passes through portions of the linked list:

• First pass: The loop for _ in range(k - 1) moves the fast pointer k-1 steps forward, taking O(k) time.
• Second pass: The while fast.next loop moves both fast and slow pointers until fast reaches the last node. Since fast is already at the k-th node, it needs to traverse n - k more nodes to reach the end, taking O(n - k) time.
• The value swap operation p.val, q.val = q.val, p.val takes O(1) time.

Total time: O(k) + O(n - k) + O(1) = O(n)

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Four pointer variables: fast, slow, p, and q
• No additional data structures are created
• The swap operation is done in-place by exchanging values

All operations are performed using a fixed number of variables regardless of the input size, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Finding the kth Node

Pitfall: A common mistake is confusion about 1-based vs 0-based indexing. Developers might incorrectly move the pointer k times instead of k-1 times to reach the kth node from the beginning.

Incorrect approach:

# Wrong: This moves k steps, landing on the (k+1)th node
for _ in range(k):
    fast_pointer = fast_pointer.next

Correct approach:

# Correct: Move k-1 steps to reach the kth node (1-indexed)
for _ in range(k - 1):
    fast_pointer = fast_pointer.next

2. Not Handling Edge Cases

Pitfall: The code might fail when:

• The linked list has only one node
• k equals the length of the list (swapping first and last nodes)
• k is at the middle of an odd-length list (swapping a node with itself)

Solution: The current implementation naturally handles these cases because:

• For single node: Both pointers point to the same node, swapping has no effect
• For k = n: The algorithm correctly identifies first and last nodes
• For middle node: Both pointers converge to the same node, self-swap is harmless

3. Attempting to Swap Nodes Instead of Values

Pitfall: Trying to swap the actual nodes by manipulating pointers is significantly more complex and error-prone:

# Complex and error-prone approach
# Need to track previous nodes, handle head changes, etc.
prev_p.next = q
prev_q.next = p
temp = p.next
p.next = q.next
q.next = temp

Better approach: Simply swap the values:

# Simple and clean
kth_from_start.val, kth_from_end.val = kth_from_end.val, kth_from_start.val

4. Incorrect Distance Calculation for kth Node from End

Pitfall: Misunderstanding how the two-pointer technique maintains the correct distance:

# Wrong: Starting slow_pointer movement too early or late
slow_pointer = head
for _ in range(k):  # Wrong offset
    fast_pointer = fast_pointer.next

Correct approach: After positioning fast_pointer at the kth node (k-1 moves), moving both pointers together maintains exactly the right gap to find the kth node from the end.