複製帶隨機指針的鏈表

作者：Grey

原文地址：

題目描述
一種特殊的單鏈表節點類描述如下

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:複製帶隨機指針的鏈表

算法和數據結構筆記

Tags: leetcode 數據結構算法算法和數據結構鏈表