Swapping Nodes in a Linked List

Problem#

Swap the values of the kth node from the beginning and the kth from the end of a singly linked list. Return the head.

Examples#

[1,2,3,4,5], k = 2 → [1,4,3,2,5]

Constraints#

1 <= k <= length.

Approach#

Single pass. Walk kth to the kth node (front pointer). Then walk a second pointer from head while kth finishes its traversal — the gap of length - k lands the second pointer on the kth-from-end node. Swap values.

Solution#

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

func swapNodes(head *ListNode, k int) *ListNode {
  p := head
  for i := 1; i < k; i++ {
    p = p.Next
  }
  first, second := p, head
  for p.Next != nil {
    p = p.Next
    second = second.Next
  }
  first.Val, second.Val = second.Val, first.Val
  return head
}

from typing import Optional

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

var swapNodes = function(head, k) {
    let p = head;
    for (let i = 1; i < k; i++) p = p.next;
    let first = p, second = head;
    while (p.next) {
        p = p.next;
        second = second.next;
    }
    [first.val, second.val] = [second.val, first.val];
    return head;
};

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode p = head;
        for (int i = 1; i < k; i++) p = p.next;
        ListNode first = p, second = head;
        while (p.next != null) {
            p = p.next;
            second = second.next;
        }
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
        return head;
    }
}

function swapNodes(head: ListNode | null, k: number): ListNode | null {
    let p: ListNode = head as ListNode;
    for (let i = 1; i < k; i++) p = p.next as ListNode;
    const first: ListNode = p;
    let second: ListNode = head as ListNode;
    while (p.next) {
        p = p.next;
        second = second.next as ListNode;
    }
    [first.val, second.val] = [second.val, first.val];
    return head;
}

Editorial#

Same gap-of-k technique used for “nth from end”. After we anchor first at the kth node and walk a second pointer in lockstep with the rest of the traversal, the second pointer is automatically at length - k, which 1-indexed is the kth from end. Swapping values avoids any pointer surgery.

Complexity#

Time: O(n).
Space: O(1).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#