Swapping Nodes in a Linked List

How it works

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.

Steps

1. Traverse with cur, decrementing k each step.
2. When k equals 1, save cur as left and set right to head.
3. Continue traversing. If right exists, advance it along with cur.
4. When cur reaches the end, right will be at the k-th node from the end.
5. Swap the values of left and right.
6. Return the head.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

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.

from typing import Optional

# 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 head

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode* left = nullptr;
        ListNode* right = nullptr;
        ListNode* cur = head;

        while (cur) {
            if (right) {
                right = right->next;
            }
            if (k == 1) {
                left = cur;
                right = head;
            }
            k--;
            cur = cur->next;
        }

        swap(left->val, right->val);
        return head;
    }
};