LeetCode138-复制带随机指针的链表

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/copy-list-with-random-pointer/

中文链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

题目详述

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

示例：

1
2
3
4
5
6
输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

提示：

你必须返回给定头的拷贝作为对克隆列表的引用。

题目详解

整个复制过程分为三个步骤：

  1. 复制每个结点并插入到它的后面。
  2. 更改新建结点的 random 指针。
  3. 分离得到原链表和新链表。

时间复杂度为 O(n)，空间复杂度为 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class LeetCode_00138 {

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // 复制每个结点并插入到它的后面
        Node node = head;
        while (node != null) {
            Node copy = new Node(node.val, node.next, node.random);
            node.next = copy;
            node = copy.next;
        }
        // 更改新建结点的 random 指针
        node = head;
        while (node != null) {
            node.next.random = node.random != null ? node.random.next : null;
            node = node.next.next;
        }
        // 分离得到原链表和新链表
        Node copiedHead = head.next;
        node = copiedHead;
        while (head != null) {
            head.next = head.next.next;
            head = head.next;
            node.next = head != null ? head.next : null;
            node = node.next;
        }
        return copiedHead;
    }

    class Node {
        public int val;
        public Node next;
        public Node random;

        public Node() {}

        public Node(int _val, Node _next, Node _random) {
            val = _val;
            next = _next;
            random = _random;
        }
    }
}