聊一聊复制链表的复制

时间:2022-02-06 14:54:55

聊一聊复制链表的复制

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]]
  2. 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

聊一聊复制链表的复制

  1. 输入:head = [[1,1],[2,1]]
  2. 输出:[[1,1],[2,1]]

示例 3:

聊一聊复制链表的复制

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

参考链接: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