leetcode【138】复制带随机指针的链表（本人感觉很好的一道题）

阳光穿透心脏的1/2处 2021-10-03 01:36 140阅读 0赞

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 \[val, random\_index\] 表示：

val：一个表示 Node.val 的整数。  
random\_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。

示例 1：

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

输入：head = \[\[1,1\],\[2,1\]\]  
输出：\[\[1,1\],\[2,1\]\]  
示例 3：

输入：head = \[\[3,null\],\[3,0\],\[3,null\]\]  
输出：\[\[3,null\],\[3,0\],\[3,null\]\]  
示例 4：

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

解题思路：第一种：利用链表单独进行复制，步骤先进行普通链表的复制，然后复制随机指针，最后再进行拆链。

第二种：以用map的映射关系，先创建一个链表并且进行映射，然后利用key.random找到随即指针的值，进行新链表随机指针的赋值，就好了。

个人感觉方法二简单，但是链表的深拷贝有助于你理解Java引用的操作，所以都会比较好。

代码展示：

map

class Solution {
        public Node copyRandomList(Node head) {
            if(head == null)
                return null;
            Map<Node, Node> mp = new HashMap<>();
            Node newH, newT;
            newH = newT = null;
            Node cur = head;
            while(cur != null){
                Node node = new Node(cur.val);
                if(newH == null){
                    newH = newT = node;
                }else
                {
                    newT.next = node;
                    newT = newT.next;
                }
                //构建一个映射关系
                mp.put(cur, node);
                cur = cur.next;
            }
            //构建随机指针
            cur = head;
            newT = newH;
            while(cur != null){
                if(cur.random != null){
                    newT.random = mp.get(cur.random);
                }else
                {
                    newT.random = null;
                }
                cur = cur.next;
                newT = newT.next;
            }
            return newH;
        }
    }

直接复制法：

class Solution {
         public static Node copyRandomList(Node head) {
            if(head == null){
                return null;
            }
    //普通链表的复制
            Node cur = head;
            while (cur != null){
                Node node = new Node(cur.val);
                node.next = cur.next;
                cur.next = node;
                cur = cur.next.next;
            }
    //随机指针的复制
            cur = head;
            while (cur != null){
                if(cur.random != null){
                cur.next.random = cur.random.next;//新的结点哦
            }
                cur = cur.next.next;
            }
    //进行拆链
            cur = head;
            Node nHead = head.next;
            while (cur != null){
                Node node = cur.next;
                cur.next = node.next;//旧断
                if(node.next != null) {
                    node.next = cur.next.next;//新断
                }
                cur = cur.next;
            }
            return nHead;
        }
    }