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

力扣地址：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
这是一道中等难度的链表题，我用两种方式解答

使用额外空间

思路

1. 使用Map<Node,Node> 来存储原始节点和深度拷贝的节点之间的关系
2. 遍历链表，然后根据链表节点去map中获取克隆节点，此时就可以设置next节点和random节点
3. 返回map.get(head)

代码如下

import java.util.HashMap;
import java.util.Map;

public class CopyRandomList {

    public static void main(String[] args) {
        Node node1 = new Node(11);
        Node node2 = new Node(22);
        Node node3 = new Node(33);
        node1.next = node2;
        node2.next = node3;
        node1.random = node3;
        node2.random = node1;
        new CopyRandomList().copyRandomList(node1);
    }

    public Node copyRandomList(Node head){
        if(head == null)
            return null;
        Map<Node,Node> map = new HashMap<>();

        Node cur = head;
        // 遍历链表，写入map
        while (cur != null){
            Node copyNode = new Node(cur.val);
            map.put(cur,copyNode);
            cur = cur.next;
        }
        // 从链表头开始，再次遍历
        cur = head;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}

重点在于第二个while遍历

// map.get(cur)得到的是当前节点的克隆节点，也就是设置克隆节点的下一个节点
// 克隆节点的下一个节点就是 当前节点的下一个节点的克隆节点
map.get(cur).next = map.get(cur.next);
// 设置当前克隆节点的random指针指向，所以我们需要找到当前节点的random指向的节点的克隆节点即可
map.get(cur).random = map.get(cur.random);

结果

不使用额外的空间

1. 遍历链表，深度拷贝当前节点，并将当前节点插入链表中

   
   拷贝出节点1，并插入链表中
   

   以此类推，行程一个新的链表

   
   新的链表

2. 接下来设置random节点，从新的链表中两两去除节点

   
   设置第一个克隆节点的random节点
   

   设置完random后的效果

   
   random设置完毕

3. 接下来需要将新链表进行拆分，将原始节点和克隆节点进行拆分

   
   image.png

4. 返回newHead，解题完毕

代码如下

public class CopyRandomList {
    public static void main(String[] args) {
        Node node1 = new Node(11);
        Node node2 = new Node(22);
        Node node3 = new Node(33);
        node1.next = node2;
        node2.next = node3;
        node1.random = node3;
        node2.random = node1;

        new CopyRandomList().copyRandomList(node1);
    }

    public Node copyRandomList(Node head) {
        Node cur = head;
        // 将拷贝的节点插入链表中
        while (cur != null){
            Node next = cur.next;
            Node newNode = new Node(cur.val+1);
            cur.next = newNode;
            newNode.next = next;
            cur = next;
        }
        // set random
        // 每次取两个节点
        cur = head;
        while (cur != null){
            // 每次读取两个节点，也就是 cur 和 next，其中next是拷贝出来的节点
            Node next = cur.next;
            // 设置克隆节点的random节点，该random节点也就是cur原始节点的random的下一个节点
            next.random = cur.random != null ? cur.random.next : null;
            // 指针下移
            cur = next.next;
        }

        // 链表拆分
        Node oldNode = head;
        Node newNode = head.next;
        Node headOld = head.next;
        while (oldNode != null){
            oldNode.next = oldNode.next.next;
            newNode.next = newNode.next != null ? newNode.next.next : null;
            oldNode = oldNode.next;
            newNode = newNode.next;
        }
        return headOld;
    }


    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}

总结

我们在解链表题的时候，尝尝会考虑使用额外的空间，这也是我们经常能想到的思路，也是比较容易实现的思路，如果在AC的时候，这个方法是没问题的，但是面对面试官，如果你给出最少使用空间的最优解，你就能脱颖而出，本文两种解法，第二种应该会更吸引面试官的眼球。如果有更好的办法，欢迎指出，互相学习。