Bookings are stored as a linked list in the order they were made. Write a function that removes the booking that is k-th from the end (k = 1 is the last one) and returns the head of the updated list. You can assume 1 <= k <= length of the list.
Write remove_kth_from_end(head, k) in Python or removeKthFromEnd(head, k) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 18 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Two passes is easy
Count the nodes (n), then walk to node n - k - 1 and unlink the one after it. That's correct and O(n), but takes two passes, and needs special handling when the head itself is removed.
Step 2
Keep a gap of k
Put two pointers on the list. Move fast k nodes ahead first. Then move both one step at a time. The gap stays k, so when fast falls off the end, slow is exactly k nodes from the end.
Step by step1 / 6
slowfast
d
10
20
30
40
50
null
Both start at the dummy.
Step 3
Stop one node earlier
To unlink a node, you need the node before it. So you want slow to stop one node before the target. Start both pointers at a dummy node in front of the head, and move fast until fast.next is empty instead of until fast is empty.
Step 4
Removing the head
With the dummy in front, removing the first node is just dummy.next = dummy.next.next: no special case. Return dummy.next, not head.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Create a dummy before the head and set fast = slow = dummy. Move fast forward k times. Then move both until fast.next is empty. Now slow.next is the node to remove: set slow.next = slow.next.next. Return dummy.next.
python
1def remove_kth_from_end(head, k):
2 dummy = ListNode(0, head)
↑so removing the head is no special case
3 fast = slow = dummy
4 for _ in range(k):
↑give fast a head start of k
5 fast = fast.next
6 while fast.next:
↑stop fast on the LAST node
7 fast, slow = fast.next, slow.next
8 slow.next = slow.next.next # unlink the k-th from the end
↑skip over the k-th from the end
9 return dummy.next
javascript
1function removeKthFromEnd(head, k) {
2 const dummy = new ListNode(0, head)
↑so removing the head is no special case
3 let fast = dummy
4 let slow = dummy
5 for (let i = 0; i < k; i++) fast = fast.next
↑give fast a head start of k
6 while (fast.next) {
↑stop fast on the LAST node
7 fast = fast.next
8 slow = slow.next
9 }
10 slow.next = slow.next.next // unlink the k-th from the end
↑skip over the k-th from the end
11 return dummy.next
12}
Complexity
TimeO(n)SpaceO(1)
O(n) time in a single pass, and O(1) extra space.
What we learned
"k-th from the end" in one pass: two pointers with a fixed gap.
To delete a node, stop at the node before it.
A dummy head turns "remove the head" into the normal case. Test k = 1 and k = length.