Remove Kth Node From End

Tags

Remove Kth Node From End

Category

Linked Lists

Difficulty

Medium

Problem Statement

Given the head of a singly linked list and a positive integer k, remove the kth node from the end of the list. The removal should be done in place. Note that the head of the list could be the node that needs to be removed.

Intuition

Using two pointers separated by a gap of k nodes, when the leading pointer reaches the end of the list, the trailing pointer will be right before the node to remove. This allows us to find and remove the target node in a single pass without first calculating the length of the list.

Approach

  1. Initialize two pointers, first and second, both at the head.
  2. Advance first by k steps so that it is k nodes ahead of second.
  3. If first is now null, the node to remove is the head itself. Update the head's value and next pointer.
  4. Otherwise, advance both first and second one step at a time until first.next is null.
  5. Now second is the node right before the target. Set second.next = second.next.next.

Pseudocode

function removeKthNodeFromEnd(head, k):
    first = head
    second = head

    // Advance first by k steps
    for i from 0 to k - 1:
        first = first.next

    // If first is null, remove the head
    if first is null:
        head.value = head.next.value
        head.next = head.next.next
        return

    // Advance both until first reaches the last node
    while first.next is not null:
        first = first.next
        second = second.next

    // Remove the node after second
    second.next = second.next.next

Time & Space Complexity

  • Time: O(n) where n is the length of the list. We traverse the list once.
  • Space: O(1) — only two pointers are used.

Key Insights

  • The two-pointer gap technique converts a "distance from end" problem into a "distance from another pointer" problem.
  • Removing the head node is a special case that requires careful handling since we cannot modify what head points to from outside the function. Instead, we copy the next node's value and skip it.
  • The gap of exactly k ensures that when first reaches the end, second is positioned correctly for removal.

Edge Cases

  • Removing the head node (k equals the length of the list).
  • Removing the last node (k = 1).
  • Single-node list where k = 1: the list becomes empty, but handling depends on the problem's API.
  • k is guaranteed to be valid (1 <= k <= length of list), so no bounds checking is needed.

Linked mentions