题目描述

解法一：通过哈希表辅助查找

第⼀步先复制结点的值，针对原始链表上的每个结点 N，在新链表上创建对应的结点 N’ 并复制 N的值，同时我们把<N， N’>的配对信息放到⼀个哈希表中。第⼆步是复制结点的指针，把这些复制链表上新创建出来的结点⽤ next指针链接起来，并设置复制链表上每个结点的 random指向。如果在原始链表中结点 N的 random指向结点S， 那么在复制链表中， 对应的N’的 random应该指向S’。 由于有了哈希表， 我们可以⽤O(1) 的时间根据 S找到 S’。

Java

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { // 主要构造函数需要传入节点值作为参数 this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { if(head == null) return null; HashMap<Node, Node> map = new HashMap<> (); // 创建哈希表，存放原始链表和复制链表中每个节点的配对关系 Node cur = head; // 1.复制结点值 while(cur != null) { Node clone = new Node(cur.val); // 创建新节点，复制老节点的值 map.put(cur, clone); // 存储<key,value1> cur = cur.next; } // 2.复制结点的指向 cur = head; // 重新回到原始链表的头结点开始顺序遍历 while(cur != null) { map.get(cur).next = map.get(cur.next); //新结点 next指向同老结点的 next指向 map.get(cur).random = map.get(cur.random); //新结点 random指向同老结点的 random指向 cur = cur.next; } // 返回复制链表的头结点，通过原始链表的 head和哈希表查找到 return map.get(head); } }

复杂度分析

时间复杂度：O(n)，遍历一遍原始链表复制新链表的节点值需要 O(n)的时间 + 再遍历一遍原始链表复制新链表的指针指向也需要 O(n)的时间，O(2*n) 即O(n) 空间复杂度：O(n)，⽤空间换时间的思想，对于有 n个结点的链表需要⼀个大小为O(n) 的哈希表。

解法二：不用辅助空间实现O(n)的查找效率

第⼀步仍然是根据原始链表的每个结点 N创建对应的 N’。不过，这次我们把复制后的新节点 N’连接在 N的后面。第二步复制原始链表上节点的 random 指针，如果原始链表上的结点 N的 random指针指向结点 S， 则它对应的复制结点 N’的 random指针指向 S的下⼀结点 S’。第三步把这个长链表拆分成两个链表： 把奇数位置的结点⽤ Next链接起来就是原始链表， 把偶数位置的结点⽤ Next 链接起来就是复制出来的链表。

Java

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { if(head == null) return null; copyNode(head); copyRandomDirect(head); return reList(head); } // 复制链表 public void copyNode(Node head) { Node cur = head; while(cur != null) { Node clone = new Node(cur.val); // 创建新节点并复制结点值 // 新节点接在老节点后面 clone.next = cur.next; cur.next = clone; cur = clone.next; } } // 复制原始链表中的随机指针 public void copyRandomDirect(Node head) { Node cur = head; while(cur != null) { Node clone = cur.next; if(cur.random != null) clone.random = cur.random.next; cur = clone.next; } } // 重新连接链表，把原始链表和新链表拆分出来 public Node reList(Node head) { Node cloneNode = head.next; Node cloneHead = head.next; // 记录新链表的头结点 head.next = cloneNode.next; head = head.next; while(head != null) { cloneNode.next = head.next; cloneNode = cloneNode.next; head.next = cloneNode.next; head = head.next; } return cloneHead; } }

复杂度分析

时间复杂度：O(n)，三趟顺序遍历分别需要 O(n)的时间，O(3*n) 即O(n) 空间复杂度：O(1)

参考

https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/fu-za-lian-biao-de-fu-zhi-jian-dan-yi-dong-de-san-/

图解 链表的深拷贝

https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-by-leetcod/