Remove the Kth Last Node From a Linked List
Given the head of a singly linked list and an integer k, remove the
k-th node counting from the end of the list (the last node is
k = 1), and return the head of the resulting list. Do this in a
single pass through the list.
Example 1
Input: 1 -> 2 -> 3 -> 4 -> 5 -> None, k = 2
Output: 1 -> 2 -> 3 -> 5 -> None
(the 2nd-from-last node, 4, is removed)
Example 2
Input: 1 -> None, k = 1
Output: None
Example 3
Input: 1 -> 2 -> None, k = 2
Output: 2 -> None
(removing the head)
Constraints
- The number of nodes is
n, with1 <= n <= 10^5. 1 <= k <= n(k is always valid for the given list).- Aim for O(n) time using a single pass and O(1) extra space.
The naive approach computes the list length first, then walks again to
find the node to remove — two passes. The one-pass trick is to use two
pointers offset by k steps: advance a fast pointer k steps ahead
first, then move fast and slow together until fast reaches the
end. At that point slow is exactly k nodes behind fast, which
means slow is positioned right before the node that needs removal.
Using a dummy head node before the real head avoids a special case
when the node to remove is the head itself (i.e., when k == n).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def remove_kth_from_end(head: ListNode | None, k: int) -> ListNode | None:
dummy = ListNode(0, head)
fast = dummy
slow = dummy
# Move fast k steps ahead of slow.
for _ in range(k):
fast = fast.next
# Move both until fast falls off the end; slow lands just
# before the node that must be removed.
while fast.next is not None:
fast = fast.next
slow = slow.next
slow.next = slow.next.next # unlink the target node
return dummy.next
Complexity: O(n) time — a single pass with two pointers, no
re-walking. O(1) extra space, since only a constant number of pointer
variables and one dummy node are allocated regardless of n.
Share this question