杭州网站建设宣盟网络/网站搜索引擎优化诊断

「剑指Offer 35.复杂链表的复制」

题目描述(level 中等)

请实现 copyRandomList函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针指向链表中的任意节点或者null。给定带有随机指针的Node结构如下：

public class Node {private int val;private Node next;private Node random;public Node(int val) {this.val = val;this.next = null;this.random = 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。

思路分析(哈希表)

观察给定的Node结构发现与普通的意义上的链表结构仅仅是多了随机指针random，而单链表在遍历的过程中只能逐一而下，不能随机访问。普通链表复制时，没有问题，只要构建节点的前驱与后继节点即可。但是这里多了一个随机节点，可能是null也可能是链表中任何一个节点。前面提到了，如果这些节点可以随机访问那这个问题就很好解决了，由此可以想到，我们可以先将节点存储下来，需要的时候拿过来用即可。考虑使用hash表在首次遍历时先将待复制的节点所对应的值value保存下来，并与原链表一一对应。

代码实现(Hash表)

class Solution {public Node copyRandomList(Node head) {if (null == head) {return null;}Map<Node, Node> nodeNodeMap = new HashMap<>();Node current = head;//将链表的值复制构建hash表,与原链表保持一致while (null != current) {nodeNodeMap.put(current, new Node(current.val));current = current.next;}//处理指向关系current = head;while (null != current) {//注意这里构建hash表时是以原表的Node为键，而新复制的链表首次遍历时仅仅保存了值，没有指向关系nodeNodeMap.get(current).next = nodeNodeMap.get(current.next);nodeNodeMap.get(current).random = nodeNodeMap.get(current.random);current = current.next;}return nodeNodeMap.get(head);}
}

思路总结

• 以原链表节点Node为Key，值Value为复制后的链表Node构建Hash表。
• 首次遍历时，将节点一一保存，新复制的节点保存对应value，没有对应关系
• 第二次遍历，通过原链表的节点Node(key)获取新节点并确定next与random的指向关系。
• 从哈希表中返回新复制的链表(key即为head)。

思路分析(拼接+拆分)

哈希表的思路简单来说就是保存下了所有的节点，那么可不可以在不引入哈希表的情况下复制链表，降低空间复杂度呢？借助哈希表的思路，在链表基础上复制一份拼接，首次遍历时不处理random指向。第二次遍历时处理新链表的random随机指向。最后将两个链表进行拆分开，同时还原原链表(对原链表尾指向进行单独处理)。

代码实现(拼接+拆分)

class Solution {public Node copyRandomList(Node head) {if (head == null) return null;Node current = head;//1.复制各节点，并构建拼接链表while (current != null) {Node tmp = new Node(current.val);tmp.next = current.next;current.next = tmp;current = tmp.next;}//2.构建各新节点的 random 指向current = head;while (current != null) {if (current.random != null) {//这里很好理解，因为是在原链表的基础进行拼接的，新节点随机节点即是当前节点的随机节点的next节点current.next.random = current.random.next;}current = current.next.next;}//3.拆分两链表current = head.next;Node prev = head, res = head.next;while (current.next != null) {prev.next = prev.next.next;current.next = current.next.next;prev = prev.next;current = current.next;}//4.对原链表的尾节点进行还原处理prev.next = null; //5.返回新链表头节点return res;     }
}

示意图

思路总结

• 复制各节点，并构建拼接链表，构建完成后，链表的长度是原链表长度的两倍

• 构建各新节点的 random 指向，因为是在原链表的基础进行拼接的，新节点随机节点即是当前节点的随机节点的next节点，可以理解为将整体向右移动了一位，而随机节点作为整体的一部分，自然可以得出current.next.random = current.random.next;

• 拆分两链表

• 对原链表的尾节点进行还原处理

• 返回新链表头节点，得到新复制的链表

时间复杂度

• 哈希表

时间复杂度O(N)：对链表进行了两次遍历，没有嵌套，时间复杂度与链表长度有关

空间复杂度O(N)：引入哈希表，空间复杂度与链表长度成线性关系

• 拼接+拆分

时间复杂度O(N)：对链表进行三次独立遍历，时间复杂度与其长度有关

空间复杂度O(1)：未引入新结构，原链表中拼接，临时节点变量空间占用为常数级

链接

LeetCode