Swapping Nodes in a Linked List — Find Kth from Front and Back

Sanjeev SharmaSanjeev Sharma
1 min read

Advertisement

Problem 232 · Swapping Nodes in a Linked List

Difficulty: Medium · Pattern: Two Pointers for kth from end

Swap values of kth node from beginning and kth node from end.

Solutions

# Python
def swapNodes(head, k):
    fast = head
    for _ in range(k-1): fast = fast.next
    front = fast  # kth from start
    slow = head
    while fast.next:
        slow = slow.next; fast = fast.next
    # slow is now kth from end
    front.val, slow.val = slow.val, front.val
    return head
// Java
public ListNode swapNodes(ListNode head, int k) {
    ListNode fast = head;
    for (int i = 1; i < k; i++) fast = fast.next;
    ListNode front = fast, slow = head;
    while (fast.next != null) { fast = fast.next; slow = slow.next; }
    int tmp = front.val; front.val = slow.val; slow.val = tmp;
    return head;
}
// C++
ListNode* swapNodes(ListNode* head, int k) {
    ListNode *fast=head, *slow=head, *front=nullptr;
    for (int i=1; i<k; i++) fast=fast->next;
    front=fast;
    while (fast->next) { fast=fast->next; slow=slow->next; }
    swap(front->val, slow->val);
    return head;
}

Complexity

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

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro