複雜連結清單的複制

題目描述：有一個複雜連結清單，其結點除了有一個Next指針指向下一個結點外，還有一個random指向連結清單中的任意結點或者NULL。其連結清單的定義如下：

public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
           

請實作 public RandomListNode Clone(RandomListNode pHead) 函數實作克隆一個連結清單。

解決思路：

• 暴力的解法：首先隻複制連結清單，不管random指針。然後再周遊原連結清單，複制random指針。複制random指針的方法是根據原連結清單從頭開始，而指向複制連結清單的指針也同時開始，判斷random指針是指向哪一個結點，然後根據位置對應，把複制連結清單的指針的位置指派給random。好吧，其實畫個圖很簡單。

  

import java.util.*;

public class Main {

    class RandomListNode{
        public int label;
        public RandomListNode next = null;
        public RandomListNode random = null;

        public RandomListNode(int label){
            this.label = label;
        }
    }

    public RandomListNode Clone(RandomListNode pHead){
        if(pHead == null)
            return null;
        RandomListNode temp = pHead;
        RandomListNode head = new RandomListNode(temp.label);
        RandomListNode p = head;
        if(temp.next != null)
            temp = temp.next;
        //首先把隻複制基本的連結清單

        while (temp != null){
            RandomListNode node = new RandomListNode(temp.label);
            p.next = node;
            node.next = null;
            p = p.next;
            temp = temp.next;
        }
        //然後複制random指針
        p = head;
        temp = pHead;
        while (p != null){
            if(temp.random == null){
                p.random = null;
                p = p.next;
                temp = temp.next;
                continue;
            }

            RandomListNode t = pHead;
            RandomListNode q = head;
            while(t != null){ //t和q隻需要判斷一個就行
                if(temp.random == t)
                    break;
                t = t.next;
                q = q.next;
            }

            p.random = q;
            p = p.next;
            temp = temp.next;
        }
        return head;
    }

    public static void main(String[] args) {
        RandomListNode node1 = new Main().new RandomListNode(1);
        RandomListNode node2 = new Main().new RandomListNode(2);
        RandomListNode node3 = new Main().new RandomListNode(3);
        RandomListNode node4 = new Main().new RandomListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;
        node1.random = null;
        node3.random = node1;
        RandomListNode head = new Main().Clone(node1);
        System.out.println(head);
        System.out.println(head.random);
        head = head.next;
        System.out.println(head.random);
        head = head.next;
        System.out.println(head.random);
    }
}

           

• 本題一種巧妙的解法是，将每個複制後的結點都跟在原結點後面，步驟如下：

  1.複制每個結點，如複制結點A得到A1，并将A1插到結點A後面。

  2.重新周遊連結清單，複制老結點的随機指針給新結點，如A1.random = A.random.next

  3.拆分連結清單，将原連結清單拆分成原連結清單和複制後的連結清單

import java.util.*;

public class Main {

    class RandomListNode{
        public int label;
        public RandomListNode next = null;
        public RandomListNode random = null;

        public RandomListNode(int label){
            this.label = label;
        }
    }

    public RandomListNode Clone(RandomListNode pHead){
        if(pHead == null)
            return null;
        RandomListNode currentNode = pHead;
        //1.複制每個結點，如複制結點A得到A1，将A1插到A後面
        while (currentNode != null){
            RandomListNode copyNode = new RandomListNode(currentNode.label);
            RandomListNode p = currentNode.next;
            copyNode.next = p;
            currentNode.next = copyNode;
            currentNode = p;
        }

        //2.重新周遊連結清單，複制老結點的随機指針給新結點，如A1.random = A.random.next
        currentNode = pHead;
        while (currentNode != null){
            currentNode.next.random = (currentNode.random == null) ? null : currentNode.random.next;
            currentNode = currentNode.next.next;
        }

        //3.拆分連結清單，将原連結清單拆分成原連結清單和複制後的連結清單
        currentNode = pHead;
        RandomListNode copyHead = currentNode.next;
        while (currentNode != null){
            RandomListNode p = currentNode.next;
            currentNode.next = p.next;
            if(p.next != null)
                p.next = p.next.next;
            currentNode = currentNode.next;
        }
        return copyHead;
    }

    public static void main(String[] args) {
        RandomListNode node1 = new Main().new RandomListNode(1);
        RandomListNode node2 = new Main().new RandomListNode(2);
        RandomListNode node3 = new Main().new RandomListNode(3);
        RandomListNode node4 = new Main().new RandomListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;
        node1.random = null;
        node3.random = node1;
        RandomListNode head = new Main().Clone(node1);
        System.out.println(head);
        System.out.println(head.random);
        head = head.next;
        System.out.println(head.random);
        head = head.next;
        System.out.println(head.random);
    }
}