hot100 138.随机链表的复制

1.题目要求：深拷贝一个链表，要求新链表中的每个节点都是新创建的，并且这些节点的random指针都指向新链表中的相应节点。

2.思路：

（1）如果没有random指针，只需要在遍历链表的同时，依此复制每个节点（创建新节点并复制val），添加在新链表的末尾。

（2）有random指针，拷贝就变得复杂了。需要知道random指向的那个节点，在新链表中是哪个节点。

（3）所以必须记录原链表节点到新链表节点的映射（map）。这样可以通过原链表random指向的节点，知道新链表的random应该指向哪个节点。

（4）难道应该使用哈希表吗？其实不需要。可以把新链表和旧链表“混在一起”。

（5）举例：有一个链表1->2->3，依次复制每个节点（创建新节点并复制val和next），把新节点直接插到原节点的后面，形成一个交错链表：1->1'->2->2'->3->3'。

（6）此时，原链表节点的下一个节点，就是其对应的新链表节点了。

（7）然后遍历这个交错链表，假如节点1的random指向节点3，那么就把节点1'的random指向节点3的下一个节点3'，这样就完成了对random指针的复制。

（8）最后，从交错链表中分离出1'->2'->3'，即为深拷贝后的链表。（注意：不能只删除节点1，2，3，因为题目要求原链表的next不能修改）。

3.复杂度分析：

（1）时间复杂度：O(n)，其中n是链表的长度。

（2）空间复杂度：O(1)，返回值不计入。

附代码：

class Solution { public Node copyRandomList(Node head) { if(head == null){ return head; } //复制每个节点，把新节点直接插到原节点的后面 for(Node cur = head;cur != null;cur = cur.next.next){ cur.next = new Node(cur.val,cur.next); //创建一个新节点：复制原节点的值，将新节点的next指向原节点的下一个节点 } //遍历交错链表中的原链表节点 for(Node cur = head;cur != null;cur = cur.next.next){ if(cur.random != null){ //要复制的random是cur.random的下一个节点 //cur表示每一个原节点 //cur.next表示每一个复制节点 //cur.next.random表示每一个复制节点的random指针 //cur.random表示每一个原节点的random指针 //cur.random.next表示每一个原节点的random指针的下一个节点，即原节点的的random指针指向节点的对应复制节点 cur.next.random = cur.random.next; } } //把交错链表分离成两个链表 Node newHead = head.next; //新链表的头是原链表头的复制节点 Node cur = head; //表示当前处理的原节点 //cur在循环外声明，是为了保证后面循环结束后仍可以访问cur for(;cur.next.next != null;cur = cur.next){ //当cur后面至少有两个节点时继续循环，因为要保证当前原节点有复制节点和下一个原节点 Node copy = cur.next; //用copy表示当前复制节点 cur.next = copy.next; //原节点指向下一个原节点 copy.next = copy.next.next; //复制节点指向下一个复制节点 } // cur.next.next == null时，循环结束，此时cur指向最后一个原节点 cur.next = null; //恢复最后一个原节点的指针指向，最后一个原节点应该指向null return newHead; } }