面试题35. 复杂链表的复制

复杂链表的复制

题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

---

示例：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

输入：

head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

---

提示：
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

转载来源：力扣（LeetCode）

---

题目分析

这题我的思路是先将普通链表复制一遍（这个不用多说了吧），复制过程中将对应的新旧节点用hashmap关联起来，再新旧链表同时遍历一遍，将旧节点指向的旧random节点，通过hashmap获取相应的新random节点，用新节点指向它即可;
国际惯例是提交完看题解，有位老哥的题解我觉得相当不错，就看着他的图复现了一遍，他的图我贴在下边；同时，我下面的代码里的smart部分就是复现的结果。

转载自：Markus-> https://leetcode-cn.com/u/markus-7/

public class Solution {
    public Node copyRandomList(Node head) {
        if(head == null)
            return null;
        HashMap<Node, Node> hashMap = new HashMap<>();
        Node copyHead = new Node(head.val);
        Node ctmpH = copyHead;
        Node tmpH = head.next;
        hashMap.put(head,ctmpH);
//        创建新的普通链表，并且将新旧节点put进map里建立联系
        while (tmpH != null) {
            Node node = new Node(tmpH.val);
            hashMap.put(tmpH,node);
            ctmpH.next = node;
            ctmpH = node;
            tmpH = tmpH.next;
        }
        tmpH = head;
        ctmpH = copyHead;
        while(tmpH != null){
            if(tmpH.random == null){
                tmpH = tmpH.next;
                ctmpH = ctmpH.next;
                continue;
            }
            ctmpH.random = hashMap.get(tmpH.random);
            tmpH = tmpH.next;
            ctmpH = ctmpH.next;
        }
        return copyHead;
    }

    public Node smartCopyRandomList(Node head) {
        if(head == null)
            return null;
        Node h = head;
//      形成一个旧新旧新交替的链表，其中旧节点的next指向新节点
        while(h != null){
            Node tmp = new Node(h.val);
            tmp.next = h.next;
            h.next = tmp;
            h = tmp.next;
        }
        h = head;
        Node ret = h.next;
//      新链表的random指向处理
        while(h != null){
            if(h.random != null)
                h.next.random = h.random.next;
            h = h.next.next;
        }
        h = head;
        while(h != null){
            Node tmp = h.next.next;
            if(tmp != null){
                h.next.next = tmp.next;
            }
            h.next = tmp;
            h = tmp;
        }
        return ret;
    }
}

代码文件

---