复杂链表的复制

2020-12-19

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

示例 1：

avatar

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

示例 2：
avatar

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

示例 3：
avatar

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

示例 4：

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

解题思路：

在原来的链表上的每个节点后面复制一个节点(先不管random节点)
重新遍历一遍链表，修改复制产生的每个节点的random节点为它前面的那个节点的random节点的下一个节点
将复制后的节点从原来的链表上一一断开，形成新的链表

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {

        if (head == null) {
            return head;
        }

        Node copyedNode = null;

        Node cur = head;
        //向后复制节点
        while (cur != null) {
            copyedNode = new Node(cur.val);
            copyedNode.next = cur.next;
            cur.next = copyedNode;

            cur = copyedNode.next;
        }

        cur = head;
        //修改每个复制节点的random节点
        while (cur != null) {
            if (cur.random != null) cur.next.random = cur.random.next;
            cur = cur.next.next;
        }

        Node dummyNode = new Node(0);
        Node curCopyed = dummyNode;
        cur = head;
        //将原来的链表与复制的链表之间的节点断开
        while (cur != null) {
            curCopyed.next = cur.next;
            cur.next = cur.next.next;//移动一步
            cur = cur.next;//移动两步
            curCopyed = curCopyed.next;//移动一步
        }
        return dummyNode.next;

    }
}

时间复杂度O(n),空间复杂度O(1)

方法二：使用哈希表，将复制生成的节点与原来的节点放入哈希表，原来的节点作为键，复制生成的节点作为值

第一步仍然是复制原始链表上的每个结点N创建N’，然后把这些创建出来的结点用Next链接起来。同时我们把<N，N’>的配对信息放到一个哈希表中。第二步还是设置复制链表上每个结点的random。如果在原始链表中结点N的 random指向结点S，那么在复制链表中，对应的N’应该指向S’。由于有了哈希表，我们可以用O（1）的时间根据S找到S’。

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true