Java算法题解LeetCode35复杂链表的复制实例

题目描述

给定一个链表，除了正常的next指针外，还有一个额外的指针random指向链表中的任意一个节点或者null。请返回这个链表的深度复制。

例如，给定链表1->2->3->4->null，random指针可能指向链表中的任意一个节点，也可能指向null。

解题思路

方法一：哈希表

一个比较暴力的做法是使用哈希表来保存原链表节点和新链表节点之间的对应关系。具体来说，对于原链表中的每个节点，我们创新一个新的节点，并存储在哈希表中，然后我们再次遍历链表，在遍历的过程中处理每个新节点的 next 和 random 指针。

步骤如下：

1. 遍历链表，将其中的每个节点都存入哈希表中。
2. 再次遍历链表，对于每个新节点，根据原链表中对应节点的下标，设置新节点的 next 指针和 random 指针。

时间复杂度为O(N)，其中N是链表中节点的数量。需要额外的空间来存储哈希表，空间复杂度也为O(N)。

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Map<Node, Node> map = new HashMap<>();
    Node newHead = new Node(head.val);
    map.put(head, newHead);
    Node p = head;
    Node q = newHead;
    while (p != null) {
        if (p.next != null) {
            if (!map.containsKey(p.next)) {
                Node newNode = new Node(p.next.val);
                map.put(p.next, newNode);
            }
            q.next = map.get(p.next);
        }
        if (p.random != null) {
            if (!map.containsKey(p.random)) {
                Node newNode = new Node(p.random.val);
                map.put(p.random, newNode);
            }
            q.random = map.get(p.random);
        }
        p = p.next;
        q = q.next;
    }
    return newHead;
}

方法二：原地修改链表

思路是先遍历原链表，对于其中的每一个节点都创建一个新的节点，并将新节点连接到原节点后面。然后再次遍历链表，通过分析原节点的random指针和新节点的next指针的关系，来设置新节点的random指针。

步骤如下：

1. 遍历链表，对于每一个节点，在该节点之后插入该节点的复制节点。

   原链表：1 -> 2 -> 3
新链表：1 -> 1' -> 2 -> 2' -> 3 -> 3'

2. 再次遍历链表，根据原节点的random指针修改新节点的random指针。

   ```
   原链表中的random指针：
   1 -> 3
   2 -> 1
   3 -> 2

   新链表中的random指针：
   1' -> 3'
   2' -> 1'
   3' -> 2'
   ```

3. 将新链表和原链表分离。

   新链表：1' -> 2' -> 3'
原链表：1 -> 2 -> 3

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

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Node p = head;
    while (p != null) {
        Node newNode = new Node(p.val);
        newNode.next = p.next;
        p.next = newNode;
        p = newNode.next;
    }
    p = head;
    while (p != null) {
        Node newNode = p.next;
        if (p.random != null) {
            newNode.random = p.random.next;
        }
        p = newNode.next;
    }
    p = head;
    Node newHead = head.next;
    while (p != null) {
        Node newNode = p.next;
        p.next = newNode.next;
        if (newNode.next != null) {
            newNode.next = newNode.next.next;
        }
        p = p.next;
    }
    return newHead;
}

示例说明

示例一

输入：1 -> 2 -> null

1 -> null
^
|
2 -> null

输出：1 -> 2 -> null

1 -> null
^
|
2 -> null

示例二

输入：2 -> 1 -> null

2 -> null
^
|
1 -> null

输出：2 -> 1 -> null

2 -> null
^
|
1 -> null