聊一聊复制链表的复制

Leetcode : https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_28_copyRandomList/Solution.java

复制链表的复制

“题目描述 ：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。难度：中等

示例 1：

1. 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
3. 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

1. 输入：head = [[1,1],[2,1]]
3. 输出：[[1,1],[2,1]]

示例 3：

1. 输入：head = [[3,null],[3,0],[3,null]]
3. 输出：[[3,null],[3,0],[3,null]]

示例 4：

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

提示：

• 10000 <= Node.val <= 10000
• Node.random 为空(null)或指向链表中的节点。
• 节点数目不超过 1000 。

方法：哈希表

“利用哈希表的查询特点，考虑构建原链表节点和新链表对应节点的键值对映射关系,再遍历构建新链表各节点的next 和random 引用指向即可。

算法流程:

• 若头节点head为空节点，直接返回null ;
• 初始化:哈希表dic ，节点cur 指向头节点;
• 复制链表:
  • 建立新节点，并向dic添加键值对(原cur节点，新cur节点) ;
  • cur 遍历至原链表下一节点;
• 构建新链表的引用指向:
  • 构建新节点的next 和random 弓|用指向;
  • cur 遍历至原链表下一节点;
• 返回值:新链表的头节点dic[cur] ;

复杂度分析:

• 时间复杂度O(N) ：两轮遍历链表，使用O(N)时间。
• 空间复杂度0(N) ：哈希表dic 使用线性大小的额外空间。

1. package com.nateshao.sword_offer.topic_28_copyRandomList;
3. import java.util.HashMap;
4. import java.util.Map;
6. /**
7. * @date Created by 邵桐杰 on 2021/12/2 14:05
8. * @微信公众号 程序员千羽
9. * @个人网站 www.nateshao.cn
10. * @博客 https://nateshao.gitee.io
11. * @GitHub https://github.com/nateshao
12. * @Gitee https://gitee.com/nateshao
13. * Description: 复杂链表的复制
14. */
15. public class Solution {
16. /**
17. * 精选解答
18. * @param head
19. * @return
20. */
21. public Node copyRandomList(Node head) {
22. if(head == null) return null;
23. Node cur = head;
24. Map map = new HashMap<>();
25. // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
26. while(cur != null) {
27. map.put(cur, new Node(cur.val));
28. cur = cur.next;
29. }
30. cur = head;
31. // 4. 构建新链表的 next 和 random 指向
32. while(cur != null) {
33. map.get(cur).next = map.get(cur.next);
34. map.get(cur).random = map.get(cur.random);
35. cur = cur.next;
36. }
37. // 5. 返回新链表的头节点
38. return map.get(head);
39. }
42. /**
43. * 思路：先复制链表的 next 节点，将复制后的节点接在原节点后，然后复制其它的
44. * 节点，最后取偶数位置的节点（复制后的节点）。
45. *
46. * @param head
47. * @return
48. */
49. public Node copyRandomList2(Node head) {
50. if (head == null) return null;
51. Node node = new Node(head.val);
52. Node temp = node;
54. while (head.next != null) {
55. temp.next = new Node(head.next.val);
56. if (head.random != null) {
57. temp.random = new Node(head.random.val);
58. }
59. head = head.next;
60. temp = temp.next;
61. }
62. return head;
63. }
65. // Definition for a Node.
66. class Node {
67. int val;
68. Node next;
69. Node random;
71. public Node(int val) {
72. this.val = val;
73. this.next = null;
74. this.random = null;
75. }
76. }
77. }

参考链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-

原文链接：https://mp.weixin.qq.com/s/g5g2Hl3W84r-SjjfjG6DNg