LeetCode Entry
19. Remove Nth Node From End of List
Remove nth node from the tail of linked list.
19. Remove Nth Node From End of List medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/527
Problem TLDR
Remove nth node from the tail of linked list.
Intuition
There is a two-pointer technique: fast pointer moves n nodes from the slow, then they go together until the end.
Approach
Some tricks:
- Use dummy first node to handle the head removal case.
- We can use counter to make it one pass. Rust borrow checker makes the task non trivial: one pointer must be mutable, another must be cloned.
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
var r: ListNode = ListNode(0).apply { next = head }
var a: ListNode? = r; var b: ListNode? = r; var i = 0
while (b != null) { if (i++ > n) a = a?.next; b = b?.next }
a?.next = a?.next?.next
return r.next
}
pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
let mut r = ListNode { val: 0, next: head }; let mut r = Box::new(r);
let mut b = r.clone(); let mut a = r.as_mut(); let mut i = 0;
while b.next.is_some() {
i+= 1; if i > n { a = a.next.as_mut().unwrap() }
b = b.next.unwrap()
}
let n = a.next.as_mut().unwrap(); a.next = n.next.clone(); r.next
}