LeetCode Entry
61. Rotate List
Rotate linked list k steps
61. Rotate List medium substack youtube
https://dmitrysamoylenko.com/leetcode/
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1350
Problem TLDR
Rotate linked list k steps
Intuition
- find the length
- find the split point k%L
- connect/disconnect
More interesting idea: make a cycle-list by connecting head to tail at the end of the first loop
Approach
- Rust doesn’t allow to make a cycle in Option<Box
> - Rust doesn’t allow to disconnect the head while holding the reference at the last item in list
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun rotateRight(h: ListNode?, k: Int): ListNode? {
h?.next ?: return h; var len = 1; var t = h
while (t?.next != null) { t = t.next; len++ }
t.next = h; for (s in 1..len - k%len) t = t?.next
return t?.next.also { t?.next = null }
}
pub fn rotate_right(mut h: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
if h.is_none() || k==0 { return h }; let (mut l, mut x) = (0, &h);
while let Some(n) = x { x = &n.next; l += 1 }
if l < 2 || k % l == 0 { return h }; let mut x = &mut h;
for _ in 0..l-(k%l) { if let Some(n) = x { x = &mut n.next }}
let mut res = x.take(); let mut x = &mut res;
while let Some(n) = x { x = &mut n.next }; *x = h; res
}