leetcode/
rotate_list.rs

1//! # 61. 旋转链表
2//!
3//! 难度 中等
4//!
5//! 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
6//!
7//! ## 示例 1:
8//!
9//! ```text
10//! 输入: 1->2->3->4->5->NULL, k = 2
11//! 输出: 4->5->1->2->3->NULL
12//! 解释:
13//! 向右旋转 1 步: 5->1->2->3->4->NULL
14//! 向右旋转 2 步: 4->5->1->2->3->NULL
15//! ```
16//!
17//! ## 示例 2:
18//!
19//! ```text
20//! 输入: 0->1->2->NULL, k = 4
21//! 输出: 2->0->1->NULL
22//! 解释:
23//! 向右旋转 1 步: 2->0->1->NULL
24//! 向右旋转 2 步: 1->2->0->NULL
25//! 向右旋转 3 步: 0->1->2->NULL
26//! 向右旋转 4 步: 2->0->1->NULL
27//! ```
28//!
29//! See [leetcode](https://leetcode-cn.com/problems/rotate-list/)
30
31use crate::ListNode;
32
33pub struct Solution;
34
35impl Solution {
36
37    /// 双指针，两个 mut 所以需要用到 unsafe
38    pub fn rotate_right(mut head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
39        debug_assert!(k >= 0);
40
41        if head.is_none() {
42            return None;
43        }
44
45        if k == 0 {
46            return head;
47        }
48
49        let mut len = 0;
50        let mut ptr = &head;
51        while let Some(ref node) = ptr {
52            len += 1;
53            ptr = &node.next;
54        }
55
56        let step = k % len;
57        if step == 0 {
58            return head;
59        }
60
61
62        let mut fast: *mut _ = &mut head;
63        let mut slow: *mut _ = fast;
64        unsafe {
65            // fast pointer go first
66            for _ in 0..step {
67                fast = &mut (*fast).as_mut().unwrap().next;
68            }
69
70            // move fast & slow together until fast reach the end
71            while (*fast).is_some() && (*fast).as_ref().unwrap().next.is_some() {
72                fast = &mut (*fast).as_mut().unwrap().next;
73                slow = &mut (*slow).as_mut().unwrap().next;
74            }
75
76            (*fast).as_mut().unwrap().next = head;
77            let new_head = (*slow).as_mut().unwrap().next.take();
78            new_head
79        }
80    }
81
82    pub fn rotate_right_unsafe(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
83        debug_assert!(k >= 0);
84
85        if head.is_none() {
86            return None;
87        }
88
89        if k == 0 {
90            return head;
91        }
92
93        let mut len = 0;
94        let mut tail = &head;
95        while let Some(ref node) = tail {
96            len += 1;
97            if node.next.is_none() {
98                break;
99            }
100            tail = &node.next;
101        }
102
103        let step = k % len;
104        if step == 0 {
105            return head;
106        }
107
108        let mut new_head = &head;
109        for _ in 0..step {
110            new_head = &new_head.as_ref().unwrap().next;
111        }
112
113        unsafe {
114            let tail = tail as *const _ as *mut Option<Box<ListNode>>;
115            let new_head = new_head as *const _ as *mut Option<Box<ListNode>>;
116            (*tail).as_mut().unwrap().next = head;
117            (*new_head).as_mut().unwrap().next.take()
118        }
119    }
120
121    /// 单指针（引用），安全版本
122    pub fn rotate_right_safe(mut head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
123        debug_assert!(k >= 0);
124
125        if head.is_none() {
126            return None;
127        }
128
129        if k == 0 {
130            return head;
131        }
132
133        let mut len = 0;
134        let mut ptr = &head;
135        while let Some(ref node) = ptr {
136            len += 1;
137            ptr = &node.next;
138        }
139
140        let step = k % len;
141
142        if step == 0 || len == 1 {
143            return head;
144        }
145
146        let mut ptr = &mut head;
147        for _ in 1..(len - step) {
148            ptr = &mut ptr.as_mut().unwrap().next;
149        }
150
151        let mut new_head = ptr.as_mut().unwrap().next.take();
152        let mut ptr = &mut new_head;
153        while ptr.is_some() && ptr.as_ref().unwrap().next.is_some() {
154            ptr = &mut ptr.as_mut().unwrap().next;
155        }
156
157        ptr.as_mut().unwrap().next = head;
158
159        new_head
160    }
161}
162
163#[cfg(test)]
164mod tests {
165    use super::*;
166    use crate::list;
167
168    #[test]
169    fn test() {
170        let cases = vec![
171            (vec![4,5,1,2,3], (list![1,2,3,4,5], 2)),
172            (vec![1,2,3,4,5], (list![1,2,3,4,5], 0)),
173            (vec![], (list![], 2)),
174            (vec![], (list![], 0)),
175        ];
176        let t = |v, k| ListNode::into_vec(Solution::rotate_right(v, k));
177        for (expect, (input, k)) in cases {
178            assert_eq!(expect, t(input, k));
179        }
180    }
181}
leetcode/rotate_list.rs

leetcode/
rotate_list.rs
