题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路

我看了下题解，大神的解法是使用map结构存放新旧结点的映射关系，使用两次遍历旧链表，第一次遍历是建立新旧结点的映射，不处理新结点的两个指针。第二次遍历才处理指针问题。他们的代码，我复写下。

public RandomListNode Clone2(RandomListNode pHead) {
        if(pHead == null)
            return null;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();//存放新旧节点的映射
        RandomListNode curr = pHead;//用来作为循环遍历的节点
        //遍历旧链表，建立新旧节点的映射
        while (pHead!= null){
            map.put(pHead, new RandomListNode(pHead.label));
            pHead = pHead.next; //遍历下一个节点
        }
        //map目前保存新旧节点的对应关系，而新链表的节点之间未建立连接关系,需要重新遍历一次
        pHead = curr;
        while (curr != null){
            if(curr.next == null){
                map.get(curr).next = null;
            }else{
                map.get(curr).next = map.get(curr.next);
            }
            if(curr.random == null){
                map.get(curr).random = null;
            }else{
                map.get(curr).random = map.get(curr.random);
            }
            curr = curr.next;
        }
        return map.get(pHead);
    }

个人解法

我的解法其实也是差不多的，也是使用map结构存放新旧结点的映射关系，只不过我存的是random指针的映射关系。先忽略random指针，其实就是普通的链表复制，然后对于random指针，如果map存放过映射，直接复用，没有就设置映射。这样时间复杂度为O(n)。上面解法也是O(n)，我少遍历了一次。

public RandomListNode Clone(RandomListNode pHead) {
        RandomListNode root = new RandomListNode(0);//新链表的头结点，并非首结点
        RandomListNode  pre = root; //新链表的尾指针
        RandomListNode  p = null;
        RandomListNode randomNode = null;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();//存放新旧结点的映射
        while (pHead != null){ //遍历旧链表的节点
            p = new RandomListNode(pHead.label);
            if(pHead.random != null){
                //查看当前的随机节点是否访问过
                if(map.containsKey(pHead.random)){
                    p.random = map.get(pHead.random);
                }else{
                    //没访问过，新建随机结点
                    randomNode = new RandomListNode(pHead.random.label);
                    p.random = randomNode;
                    map.put(pHead.random, randomNode);
                }
            }else{
                p.random = pHead.random;
            }
            pre.next = p;
            pre = p;
            pHead = pHead.next;
        }
        pre.next = null;
        return root.next;//返回新链表的首结点
    }