07.03.2024
876. Middle of the Linked List easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/531
Problem TLDR
Middle of the Linked List #easy
Intuition
Use Tortoise and Hare algorithm https://cp-algorithms.com/others/tortoise_and_hare.html
Approach
We can check fast.next
or just fast
, but careful with moving slow
. Better test yourself with examples: [1], [1,2], [1,2,3], [1,2,3,4]
.
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun middleNode(head: ListNode?): ListNode? {
var s = head; var f = s
while (f?.next != null) {
f = f?.next?.next; s = s?.next
}
return s
}
pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let (mut s, mut f) = (head.clone(), head);
while f.is_some() {
f = f.unwrap().next;
if f.is_some() { f = f.unwrap().next; s = s.unwrap().next }
}
s
}