简单题

剑指 Offer 06. 从尾到头打印链表

注意一个所有权的问题，另外这一题不需要先翻转链表

struct Solution;
impl Solution {
    /// 反转链表,顺序读取，再反向
    pub fn reverse_print(head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut res: Vec<i32> = Vec::new();
        // 我们对head拥有所有权，拿进来之后将其修改为了mut的数据，
        // 这样可行的原因是下来的直接拥有所有权，不论如何离开这个scope之后，head都没有了
        // 因此可以直接进行修改
        let mut current = head;
        while let Some(mut node) = current.take() {
            let next = node.next.take();
            res.push(node.val);
            current = next;
        }
        res.reverse();
        res
    }
}

中等

剑指 Offer 35. 复杂链表的复制

这一题乍一看感觉很简单，就是单纯的复制就行了，但是当我发现压根不能用Rust写的时候，发现问题没那么简单。如果只是简单地复制，无非就是一个虚拟头结点：

public Node copyRandomList(Node head) {
    Node cur = head;
    Node dum = new Node(0), pre = dum;
    while(cur != null) {
        Node node = new Node(cur.val); // 复制节点 cur
        pre.next = node;               // 新链表的 前驱节点 -> 当前节点
        // pre.random = "???";         // 新链表的 「 前驱节点 -> 当前节点 」 无法确定
        cur = cur.next;                // 遍历下一节点
        pre = node;                    // 保存当前新节点
    }
    return dum.next;
}

问题就在于，Random这个节点究竟指向谁？
因此第一个方法就是保存Random的值，两次遍历解决

法一：存map，两次遍历

map存储每一个节点的值，然后再一次遍历的时候顺序的新建即可：

    // 剑指 Offer 35. 复杂链表的复制
public Node copyRandomList(Node head) {
    Node cur = head;
    Map<Node, Node> map = new HashMap<>();
    // 把自己的节点存入,
    while (cur != null) {
        map.put(cur, new Node(cur.val));
        cur = cur.next;
    }
    cur = head;
    // 这个思路没想到，之前一直固化的想要使用一个dum节点来处理
    // 但是发现，很难弄，而map中的值恰恰就是我们需要的新节点
    while (cur != null) {
        map.get(cur).next = map.get(cur.next);      // now its new head
        map.get(cur).random = map.get(cur.random);  // thus, can be directly used
        cur = cur.next;
    }
    return map.get(head);
}

复杂做法：

public Node copyRandomList(Node head) {
    Node cur = head;
    Map<Node, Node> map = new HashMap<>();
    // 把自己的节点存入,
    while (cur != null) {
        map.put(cur, new Node(cur.val));
        cur = cur.next;
    }
    cur = head;
    Node res = map.get(cur);
    Node dum = new Node(0);
    dum.next = res;
    while (cur != null) {
        res.next = map.get(cur.next);
        res.random = map.get(cur.random);
        res = res.next;
        cur = cur.next;
    }
    return dum;
}