链表一般是学习 Rust 的第一关，完成一个链表对于 Rust 的所有权、借用、可变/不可变、Box、Option 等重要的基础概念都有涉及。
能够写好链表，说明对 Rust 的基础概念和思维方式都有了一定的了解。
本文所指的链表特指用 Box 实现的单向链表，仅用来熟悉 Rust 的基础知识。其基本实现为：

#[derive(Debug)]
pubstructListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

leetCode 上的链表相关题目，如 21、206、876 均只提供这种链表定义。
实际使用中，注重性能会考虑使用裸指针写链表，比如标准库里的LinkedList。
对性能要求不高可以使用 Rc/RefCell，写代码会容易很多，而且支持双向链表。

预备知识

Option

Option 是 Rust 中最常用最重要的类型，它的语义是这个类型的变量可能为 None。None 不是空指针，是一个类型，语义为空。
绝大部分变量都有可能为空的需求，比如链表的 next，最后一个节点的 next 肯定是空的。基本类型比如 i32 这种，空值可以用 0 表示。
复杂类型可能为空时，就应该使用 Option，这是 Rust 的一种最基本的设计模式。

Box

Box 相当于独占指针，只不过数据存在堆上，独占带来的后果就是，一个节点不可能被一个以上变量持有。在节点不能被克隆的情况下，就要考虑到底应该由谁来持有节点。
例如，翻转一个链表：1->2->3->4，就不能先把节点 4 的 next 指向节点 3，因为这样会导致节点 2 的 next 和节点 4 的 next 抢节点 3，这样的逻辑在 rust 中不可能通过编译，所以我们就不用浪费时间设计这种逻辑的代码了。

take/replace

操作链表，我们不可避免的要转移节点，比如合并两个链表，我们自然要把每个节点从原来的链表中拆出来，装到新的链表中。
那么问题来了，我们怎么把链表上的节点拿走？或者更具体点，我们怎么把节点的 next 的对象的所有权移走？
Rust 不允许我们留一个悬垂指针，因此 next 上一定要有些东西，最简单的方式，自然是找个成本低的东西，把我们需要的对象换出来。
take/replace 就是这种思维方式的实际应用。
take 用于 Option，可以用 None 把 Option 里的内容转移出来，取得其所有权。
take 改变了数据，因此被执行的 Option 对象必须可变，take 之后，此 Option 等于 None。
replace 使用的范围更广，很多数据结构都支持此方法，可以自己构造一个语义上的空对象来换取数据。

多个判断条件的模式解构

match/if let/while let 是 Rust 中常用的操作，可以从枚举中匹配出具体的类型，对 Option 类型用的尤其多。
但是如果要同时判断两个 Option 对象该怎么做？
可以把两个 Option 对象组成元组，再解构出来，比如：

 match (l1,l2) {
    (Some(_l1),None) => { },
    (None,Some(_l2)) => { },
    (Some(_l1),Some(_l2)) => { },
    (None,None) => { },
}

模式解构中的 ref 和 mut

如果模式解构出的数据需要修改或者借用，可以使用如下形式：


if let Some(ref mut _ret) = ret { }
if let Some(ref _ret) = ret { }
if let Some(mut _ret) = ret { }

链表实战

现在我们来实现一些链表的操作。

创建节点

使用 leetcode 提供的节点结构体定义，并实现 new 方法。
new 方法没什么好说的，next的初值设置为 None。

#[derive(Debug)]
pub struct ListNode {
    pub val:i32,
    pub next:Option<Box<ListNode>>
}
impl ListNode {
    pub fn new(val:i32) -> Self {
        return ListNode{val:val,next:None}
    }
}

追加节点

链表肯定不能只有一个节点，所以先要实现追加节点的方法。
追加节点需要能够从头节点找到尾节点，然后修改尾节点的 next 属性。

impl ListNode {
    // 想修改节点，必须返回可变借用
    pub fn getLastMut(&mut self) -> &mut Self {
        if let Some(ref mut boxNode) = self.next { 
            return boxNode.getLastMut();
        }else{
            return self;
        }
    }
    // 追加节点
    pub fn append(&mut self, val:i32){
        let _node = ListNode::new(val);
        self.getLastMut().next = Some(Box::new(_node));
    }
}

翻转链表
接下来我们实现 leetcode 206. 反转链表。
示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

翻转链表的关键，是保证不会有两个变量抢一个节点，同时所有的节点都能被访问到。
从头部开始循环翻转，循环时需要能拿到之前的一个节点和之后的一个节点，这样把当前节点的 next 指向前一个节点，然后把当前节点指向下一个节点，继续下一轮循环即可。
下一个节点可通过当前节点的 next 用 take() 取出，因此建立一个临时变量 prev 存储上一个节点，初始值自然为 None。

impl ListNode {
    pub fn reverse_list(head:Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut prev = None; // 上一个节点
        let mut cur = head; // 当前节点
        while let Some(mut _node) = cur { // 用take置换next中的节点需要 mut
            cur = _node.next.take(); // 换出 next 作为下一次的 cur
            _node.next = prev; // 把next指向前一个节点
            prev = Some(_node);  // 更新 prev
        }
        return prev;  // 跳出循环时,prev就是翻转后的头节点
    }
}

链表的中间结点
接下来我们实现 leetcode 876. 链表的中间结点
示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

一般来说，获取中间节点可以使用快慢指针，快指针每次走两步，慢指针每次走一步，快指针走到终点，慢指针即可获取中间节点。
但是在 Rust 中，使用快慢指针意味着链表要给两个指针共享，共享不可变，我们没法修改链表，就没办法把中间节点的所有权拿走作为函数的返回。
因此，只能记录中间位置，然后再进行一次遍历，在遍历到中间位置时把节点返回。

impl ListNode {
    pub  fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut head = head;
        let mut fast = &head;
        let mut total = 0;  // 获取总长度
        while let Some(_fast) = fast {
            total += 1;
            fast = &_fast.next;
        }
        if total%2 == 0 {
            total = total/2
        }else{
            total = (total-1)/2
        }
        let mut step = 0;  // 根据总长度算出中间位置
        while step < total {
            step += 1;
            if let Some(_head) = head {
                head = _head.next;
            }
        }   
        return head; 
    }
}

// 快慢指针法，快指针走两步，慢指针走一步，慢指针停下来的地方就是中间结点。

// 然而在 Rust 中，这题的语义有所不同。函数接收一个单链表，返回一个单链表，实际上是把原链表从中间截断，释放前一半，返回后一半。其他语言可以不管释放，随便泄露，或者交给 GC 处理。

// node.next.as_ref() 取后继结点的只读指针，这个指针可为空，它的类型是 Option<&Box>.

// 当快慢指针在链表上移动时，整个链表处于只读锁定状态。Rust 编译器通过生命周期追踪到：快慢指针的有效性来源于 head 不可变。如果修改 head，指针很可能失效，违反了内存安全。

// 所以我们只能先完成中间结点的定位，再释放前一半链表。在函数运行期间，中间结点的内存地址是不变的，可以用做标识。最后挨个检验结点地址，挨个释放，直到遇到中间结点，返回中间结点。

pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    letmut head = head;
    letmut slow = head.as_ref();
    letmut fast = head.as_ref();
    loop {
        ifletSome(node) = fast {
            fast = node.next.as_ref();
        } else {
            break;
        }
        ifletSome(node) = fast {
            fast = node.next.as_ref();
        } else {
            break;
        }
        ifletSome(node) = slow {
            slow = node.next.as_ref();
        } else {
            break;
        }
    }
    let mid_addr = ifletSome(node) = slow {
        node.as_ref() as *const ListNode
    } else {
        returnNone;
    };
    whileletSome(node) = head.as_ref() {
        let addr = node.as_ref() as *const ListNode;
        if addr != mid_addr {
            head = head.unwrap().next;
        } else {
            break;
        }
    }
    head
}

合并两个有序链表

接下来我们实现 leetcode 21. 合并两个有序链表
示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

两个链表都有序，合成一个链表，只要 take() 出来逐一比较，小的放入新链表，大的放回原链表，直到一个链表为空，把另外一个链表追加到尾部即可。
问题是最后要返回头节点，单向链表没法从尾部返回头节点，合并后也不可能还持有头结点。
因此，只能自己创建一个头结点，把合并的链表追加到此头结点的 next。
只要可变借用头结点即可修改 next，不需要持有头结点。
最后把头结点的 next 返回即可。

impl ListNode {
    pub fn merge_two_lists(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut retHead: Option<Box<ListNode>> = Some(Box::new(ListNode::new(-1))); // 创建一个头节点
        let mut cur= &mut retHead;
        let mut l1 = l1;
        let mut l2 = l2;
        let mut next = true;
        while next == true {
            match (l1.take(),l2.take()) {  // 取出来比较
                (Some(_l1),None) => {
                    // 只有l1了，后面不再需要遍历
                    if let Some(ref mut _cur) = cur { // ref 禁止移动，mut 确保可以修改
                        _cur.next = Some(_l1);
                    }
                    next = false;
                },
                (None,Some(_l2)) => {
                   // 只有l2了，后面不再需要遍历
                   if let Some(ref mut _cur) = cur {  // ref 禁止移动，mut 确保可以修改
                       _cur.next = Some(_l2);
                   }
                   next = false;
                },
                (Some(mut _l1),Some(mut _l2)) => {  // mut 确保可以修改
                    // 需要比大小了，先比个大小
                    if &_l1.val < &_l2.val {
                        let _next = _l1.next.take();
                        if let Some(ref mut _cur) = cur {  // ref 禁止移动，mut 确保可以修改
                            _cur.next = Some(_l1);
                            cur = &mut _cur.next; // 游标移动
                        }
                        l1 = _next;  
                        l2 = Some(_l2);  // 大的放回
                    }else{
                        let _next = _l2.next.take();
                        if let Some(ref mut _cur) = cur {
                            _cur.next = Some(_l2);
                            cur = &mut _cur.next; // 游标移动
                        }
                        l2 = _next;
                        l1 = Some(_l1);  // 大的放回
                    }
                },
                (None,None) => {
                    next = false;
                },
            }
        }
        return retHead.unwrap().next;
    }
}

旋转链表

旋转链表: 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置 ```bash 输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

输入：head = [0,1,2], k = 4
输出：[2,0,1]

链表只有一条，当将头节点指针&mut Box<ListNode>推入队列时，这根指针就已经有了修改整条链表的权利了。显然，第二个指针无法拥有mut权限了，因为不能同时存在同一内存的两个可变引用。
在上面的代码中，我第一遍老实地使用不可变引用遍历一遍链表统计链表长，什么也没有发生。
第二次遍历要用可变引用，但是并没有存储，所以是可以的。到达要切开链表的地方，我用了take()方法将这之后的结点（原先被head所拥有）转移到了由new_head所拥有。
最后将剩余的链表遍历完，将最后的None修改成head。现在head失去所有权，整条链表由new_head所拥有。
```rust
pub fn rotate_right(mut head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
    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<ListNode>> = 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<ListNode> = 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<ListNode>> = ptr.next.take(); // split
    let mut ptr: Option<&mut Box<ListNode>> = 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
}

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

调用

把上述代码保存成文件 xbox.rs，在 main.rs 写个测试调用，如下：

fn main() {
    letmut list_node = ListNode::new(1);
    list_node.append(2);
    list_node.append(3);
    list_node.append(4);
    list_node.append(5);
    list_node.append(6);
    println!("list=>{:?}", list_node);
    let list_node2 = ListNode::reverse_list(Some(Box::new(list_node)));
    println!("list2=>{:?}", list_node2);
    let list_node3 = ListNode::middle_node(list_node2);
    println!("list3=>{:?}", list_node3);
    let list_node4 = ListNode::middle_node_fast_show(list_node3);
    println!("list4=>{:?}", list_node4);
    letmut list_node5 = ListNode::new(1);
    list_node5.append(2);
    list_node5.append(7);
    letmut list_node6 = ListNode::new(1);
    list_node6.append(3);
    list_node6.append(5);
    let list_node7 =
        ListNode::merge_two_lists(Some(Box::new(list_node5)), Some(Box::new(list_node6)));
    println!("list7=>{:?}", list_node7);
    let mut list_node8 = ListNode::new(1);
    list_node8.append(2);
    list_node8.append(3);
    list_node8.append(4);
    list_node8.append(5);
    let list_node9 = ListNode::rotate_right(Some(Box::new(list_node8)), 2);
    println!("list9=>{:?}", list_node9);
}

Rust学习笔记-通过链表操作学习