[LintCode/LeetCode] Copy List with Random Pointer

Jacendfeng 發(fā)布于2019-08-14 15:32 / 3708人閱讀

摘要：大體意思就是，先復制到，順便將所有的放在再復制所有的到，順便將所有的放在最后令，令，將和分離，返回的頭結(jié)點

Problem

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Challenge

Could you solve it with O(1) space?

Note

因為O(1) space，所以no hashtable。新建兩個結(jié)點n1 n2，令n1 = head，向后循環(huán)，同時不斷復制n2到n1.next；再放回頭結(jié)點，循環(huán)第二次，復制n2.random到n1.random.next，再放回頭結(jié)點；再建立第三個結(jié)點n3 = n2，循環(huán)第三次，令n1 n2分離，返回頭結(jié)點n3，結(jié)束。

大體意思就是，先復制n1到n2，順便將所有的n2放在n1.next；再復制所有的n1.random到n2.random，順便將所有的n2.random放在n1.random.next；最后令n3 = n2，令n1 = n1.next.next, n2 = n2.next.next，將n1和n2分離，返回n2的頭結(jié)點n3.

Solution

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        RandomListNode n1 = head, n2, n3;
        while (n1 != null) {
            n2 = new RandomListNode(n1.label);
            n2.next = n1.next;
            n1.next = n2;
            n1 = n1.next.next;
        }
        n1 = head;
        n2 = n1.next;
        while (n1 != null) {
            n2.random = n1.random == null ? null : n1.random.next;
            n1 = n1.next.next;
            n2 = n1 == null ? null : n2.next.next;
        }
        n1 = head;
        n2 = n1.next;
        n3 = n2;
        while (n1 != null) {
            n1.next = n1.next.next;
            n2.next = n2.next == null ? null : n2.next.next;
            n1 = n1.next;
            n2 = n2.next;
        }
        return n3;
    }
}