题目地址(35. 复杂链表的复制)

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

题目描述

  1. 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
  5. 示例 1：
  7. 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
  8. 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
  11. 示例 2：
  13. 输入：head = [[1,1],[2,1]]
  14. 输出：[[1,1],[2,1]]
  17. 示例 3：
  19. 输入：head = [[3,null],[3,0],[3,null]]
  20. 输出：[[3,null],[3,0],[3,null]]
  23. 示例 4：
  25. 输入：head = []
  26. 输出：[]
  27. 解释：给定的链表为空（空指针），因此返回 null。
  32. 提示：
  34. -10000 <= Node.val <= 10000
  35. Node.random 为空（null）或指向链表中的节点。
  36. 节点数目不超过 1000 。
  40. 注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

前置知识


公司

  • 暂无

思路

关键点


代码

  • 语言支持：Java

Java Code:

  2. /*
  3. // Definition for a Node.
  4. class Node {
  5.     int val;
  6.     Node next;
  7.     Node random;
  9.     public Node(int val) {
  10.         this.val = val;
  11.         this.next = null;
  12.         this.random = null;
  13.     }
  14. }
  15. */
  16. class Solution {
  17.     public Node copyRandomList(Node head) {
  18.         if(head == null){
  19.             return null;
  20.         }
  21.         Node cur = head;
  22.         //1. 将链表 1->2->3  构建成 1->1->2->2->3->3
  23.         while (cur != null) {
  24.             Node temp = new Node(cur.val);
  25.             temp.next = cur.next;
  26.             cur.next = temp;
  27.             cur = cur.next.next;
  28.         }
  29.         //2. 让复制出来的链表的random = 原来的random.next
  30.         cur = head;
  31.         while (cur != null) {
  32.             if (cur.random != null) {
  33.                 cur.next.random = cur.random.next;
  34.             }
  35.             cur = cur.next.next;
  36.         }
  37.         //3. 拆分复制的链表 并将原来的链表还原
  38.         cur = head.next;
  39.         //指向初始链表的开头
  40.         Node pre = head;
  41.         //最后返回的复制的链表
  42.         Node res = head.next;
  43.         while (cur.next != null) {
  44.             //顺序不能反 如果先cur的话 pre.next.next 就会指向更改后的cur.next
  45.             pre.next = pre.next.next;
  46.             cur.next = cur.next.next;
  47.             pre = pre.next;
  48.             cur = cur.next;
  49.         }
  50.         //最后记得把初始的链表的最后一个节点指向null 不然还是指向的复制链表的最后一个
  51.         pre.next = null;
  52.         return res;
  53.     }
  54. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 35. 复杂链表的复制 - 图1#card=math&code=O%28n%29&id=AtqDT)
  • 空间复杂度：剑指 Offer 35. 复杂链表的复制 - 图2#card=math&code=O%28n%29&id=KqqSo)