在 Leetcode 中 Rust 的链表定义为

    // Definition for singly-linked list.      #[derive(PartialEq, Eq, Clone, Debug)]      pub struct ListNode {          pub val: i32,          pub next: Option<Box>      }  

需要理解的是 next 字段的类型为 Option>,这个类型不存在任何的引用,暗含的意思就是:链表头是整个链表的拥有者,负责整个链表所占据内存的管理(包括最终销毁)。

进一步说,Rust 中这样实现的链表和用 C++实现的链表是完全不同的:每个节点不再是独立存在的了,而是被先驱节点所管理,同时也管理着它的 next 字段后所有的后驱节点。

接下来看一下 LeetCode 上一道简单的旋转链表题:

    Given a linked list, rotate the list to the right by k places, where k is non-negative.      Example 1:      Input: 1->2->3->4->5->NULL, k = 2      Output: 4->5->1->2->3->NULL      Example 2:      Input: 0->1->2->NULL, k = 4      Output: 2->0->1->NULL  

简单分析例子,题意所要求的操作就是从链表中间某处切开后前后互换(inplace)。

从 LeetCode 61. Rotate List 观常规 Rust 链表操作

针对这个例子,我第一想法是用一个长度为 3 的队列遍历这条链表,每经过一个节点就将指向该节点的智能指针 Box 从队尾加入队列,超出队列长度 3 的话队头节点离开。这样的话,遍历结束后,队列中剩下指针指向的元素是 3,4,5。加上头节点,可以完成所有的操作了,好处是只需遍历一遍。

然而这样的想法用 C++写简单方便,但是并不是 think in Rust,而且 Rust 也不允许这么做。

首先我们需要使用队列中的指针对原来的链表进行操作,则推入队列的必须是 &mut; Box

到这里已经出现问题了。把一开始的思路用 rust 写出来,实际得到的是:

从 LeetCode 61. Rotate List 观常规 Rust 链表操作

链表只有一条,当将头节点指针 &mut; Box 推入队列时,这根指针就已经有了修改整条链表的权利了。显然,第二个指针无法拥有 mut 权限了,因为不能同时存在同一内存的两个可变引用。

所以说,我的这种只需遍历一遍的方法是无法在 Rust 中轻松实现的。下面给出 AC 代码,遍历了两次链表。

    impl Solution {          pub fn rotate_right(mut head: Option<Box>, k: i32) -> Option<Box> {              if head.is_none() || k <= 0 { return head }              // Step 1 - loop the linked-list and count total length (Don't need mut)              let mut ptr: Option<&Box> = head.as_ref();              let mut list_len = 0;              while let Some(node) = ptr {                  ptr = node.next.as_ref();                  list_len += 1;              }              // Step 2 - calculate the curoff place and reach that node using &mut; Box              // because this time we want to mutate the list              let cutoff_cnt = list_len - k % list_len;              if cutoff_cnt == list_len { return head }              let mut ptr: &mut Box = head.as_mut().unwrap();              let mut i = 1;              while i < cutoff_cnt {                  ptr = ptr.next.as_mut().unwrap();                  i += 1;              }              // Step 3 - Split into two list and then concatenate              // head owns one list and new_head owns the other              let mut new_head: Option<Box> = ptr.next.take();  // split              let mut ptr: Option<&mut Box> = new_head.as_mut();              while let Some(node) = ptr {                  if node.next.is_none() { ptr = Some(node); break }                  ptr = node.next.as_mut();              }              ptr.unwrap().next = head; // concatenate              new_head          }      }  

在上面的代码中,我第一遍老实地使用不可变引用遍历一遍链表统计链表长,什么也没有发生。

第二次遍历要用可变引用,但是并没有存储,所以是可以的。到达要切开链表的地方,我用了 take() 方法将这之后的结点(原先被 head 所拥有)转移到了由 new_head 所拥有。

    let mut new_head: Option<Box> = ptr.next.take();  // split  

从 LeetCode 61. Rotate List 观常规 Rust 链表操作

最后将剩余的链表遍历完,将最后的 None 修改成 head。现在 head 失去所有权,整条链表由 new_head 所拥有。

    ptr.unwrap().next = head; // concatenate  

总结:在 Rust 中定义链表,不要再认为节点是孤立的,一个结点代表的就是之后整条链。要对链进行操作,想清楚分裂后的两条链分别归谁拥有。Rust 有效地防止了环链表的出现,比如说,一个链表只有一个 next 字段指向自己的节点。(XD

https://segmentfault.com/a/1190000021699547