# 03.03.2024 [19. Remove Nth Node From End of List] medium
Remove `n`th node from the tail of linked list.
03.03.2024
19. Remove Nth Node From End of List medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/527
Problem TLDR
Remove n
th 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
}