复杂链表的复制

题目描述：有一个复杂链表，其结点除了有一个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);
    }
}