Problem statement

Given the head of a singly linked list and an integer k, swap the values of the k-th node from the beginning and the k-th node from the end (positions counted from 1), and return the head of the list.

Example 1

Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]
Explanation: The 2nd node from the front holds 2, the 2nd from the end holds 4.

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]

Example 3

Input: head = [1,2,3], k = 2
Output: [1,2,3]
Explanation: Both counts land on the middle node, so nothing changes.

Constraints

• The number of nodes in the list is n
• 1 <= k <= n <= 10^5
• 0 <= Node.val <= 100

Hints for Swapping Nodes in a Linked List

1. Hint 1

   The k-th node from the end is the (n − k + 1)-th from the front.

2. Hint 2

   To find it in one pass, walk a pointer to the k-th node first; then start a second pointer at the head and move both until the first one reaches the last node.

3. Hint 3

   The second pointer then sits on the k-th node from the end. Swap the two nodes' values.

How to solve Swapping Nodes in a Linked List

The k-th node from the front is reached by walking k - 1 steps. From there, a second pointer started at the head and moved in lockstep until the front pointer hits the last node lands on the k-th node from the end. Swapping their values finishes the job.

Approach

1. Walk first from head k - 1 steps — the k-th node.
2. Set fast = first and second = head; while fast.next exists, advance both.
3. Swap first.val and second.val; return head.

Why it works

When fast stops on the last node (position n) it has moved n - k steps from position k, so second has moved the same n - k steps from position 1 and is at position n - k + 1 — the k-th node from the end.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• When both positions coincide (the middle of an odd list) the swap is a no-op — that is correct.
• k may be larger than n / 2; the two pointers simply cross, and the swap is still right.
• Swapping values is what the problem asks for; relinking the nodes is possible but much more error-prone when they are adjacent.

Reference solution

Python

from typing import Optional

def swapNodes(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    first = head
    for _ in range(k - 1):
        first = first.next
    fast, second = first, head
    while fast.next:
        fast = fast.next
        second = second.next
    first.val, second.val = second.val, first.val
    return head

Java

public static ListNode swapNodes(ListNode head, int k) {
    ListNode first = head;
    for (int i = 1; i < k; i++) first = first.next;
    ListNode fast = first, second = head;
    while (fast.next != null) { fast = fast.next; second = second.next; }
    int t = first.val;
    first.val = second.val;
    second.val = t;
    return head;
}

C++

ListNode* swapNodes(ListNode* head, int k) {
    ListNode* first = head;
    for (int i = 1; i < k; i++) first = first->next;
    ListNode *fast = first, *second = head;
    while (fast->next) { fast = fast->next; second = second->next; }
    swap(first->val, second->val);
    return head;
}

JavaScript

var swapNodes = function(head, k) {
    var first = head;
    for (var i = 1; i < k; i++) first = first.next;
    var fast = first, second = head;
    while (fast.next !== null) { fast = fast.next; second = second.next; }
    var t = first.val;
    first.val = second.val;
    second.val = t;
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More two pointers problems

• Merge Two Sorted Linked Lists in Reverse Order Medium
• Rotate a Linked List Medium
• Segregate Even and Odd Nodes in a Linked List Medium
• Maximum Twin Sum of a Linked List Medium
• Delete the Middle Node of a Linked List Medium
• Merge In Between Linked Lists Medium