复制带随机指针的链表

作者：Grey

原文地址：

博客园：复制带随机指针的链表

CSDN：复制带随机指针的链表

题目描述
一种特殊的单链表节点类描述如下

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

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

random 指针是单链表节点结构中新增的指针，random 可能指向链表中的任意一个节点，也可能指向 null，

给定一个由 Node 节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，返回复制的新链表的头节点。

注：要求时间复杂度O(N)，额外空间复杂度O(1)

OJ见：LeetCode 138. Copy List with Random Pointer

假设原始链表如下，其中虚线表示 random 指针

由于空间复杂度需要O(1)，所以使用辅助数组的方式不可取，只能在链表上进行原地调整。

第一步，将当前节点的复制节点连在当前节点的下一个位置上，如上链表，a'为a的复制节点，其他节点同理，首先会得到如下链表

第二步，复制节点的 random 指针指向当前节点的 random 指针的下一个位置，以a节点为例，a节点的next就是a的复制节点a'，a节点的random节点的next就是a'的random指针

即a.next.random = a.random.next,由于random指针可能为空，所以a.next.random = a.random == null?null:a.random.next，其余节点类似，示例图如下

第三步，以上已经完成了链表元素的复制，接下来是分离原链表和复制链表。

以a和a'节点为例，分离的过程就是

a.next = a.next.next;
a'.next = a'.next.next;

特别要注意最后一个节点，因为最后一个节点的next为空，所以，针对最后一个节点d和d'来说

d.next = null;
d'.next = null;

最后返回复制链表的头部即可，本例中，返回a'节点即可。

完整代码见

class Solution {
    public static Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // 以下方法将每个节点的复制节点都在这个节点后面
        // 如果链表是:1->2->3->4 复制以后，会变成： 1->1->2->2->3->3->4->4
        Node cur = head;
        while (cur != null) {
            Node tmp = cur.next;
            Node copy = new Node(cur.val);
            cur.next = copy;
            copy.next = tmp;
            cur = tmp;
        }

        // 以下方法是设置每个复制节点的random指针
        cur = head;
        while (cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;
            // 无须判断cur.next是否空指针，因为cur永远是原链表的位置，cur只要不为null
            // cur.next必为复制节点，所以cur只要不为空，cur.next一定存在
            cur = cur.next.next;
        }

        // 以下方法是断开原链表和复制链表,注意最后一个节点
        cur = head;
        Node copyHead = head.next;
        Node copyCur = copyHead;
        Node start = copyHead.next;
        head.next = null;
        int i = 1;
        while (start != null) {
            Node next = start.next;
            if ((i & 1) == 1) {
                cur.next = start;
                cur = start;
            } else {
                copyCur.next = start;
                copyCur = start;
            }
            i++;
            start = next;
        }
        cur.next = null;
        copyCur.next = null;
        return copyHead;
    }
}

本题的所有图例见: processon:复制带随机指针的链表

更多#

算法和数据结构笔记