Leetcode系列之链表（3）

题目3：

现在有一个这样的链表：链表的每一个节点都附加了一个随机指针，随机指针可能指向链表中的任意一个节点或者指向空。

请对这个链表进行深拷贝

思路：

1.链表的复制的一般方法（插入复制，断裂复原），具体如下

插入断裂法复制链表

ABCD是原来的链表，abcd是复制的链表，第一遍扫描顺序复制next指针，把ABCD的next分别指向abcd，将a的next指针指向B，b的next指针指向C，依次类推

复制random指针： a->random=A->random,依此类推

恢复:A->next=a->next;a->next=a->next->next，依此类推

代码：

/**

* Definition for singly-linked list with a random pointer.

* class RandomListNode {

*    int label;

*    RandomListNode next, random;

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

* };

*/

import java.util.*;

public class Solution {

    public RandomListNode copyRandomList(RandomListNode head) {

        if(head==null){

                return null;

        }

        RandomListNode p1=head;

        while(p1!=null){

              RandomListNode p2=new RandomListNode(0);

                p2.label=p1.label;

                p2.random=null;

                p2.next=p1.next;

                p1.next=p2;

                p1=p2.next;

        }//将新节点穿插入旧链表中

        p1=head;//p1为新链表的头结点

        while(p1!=null){

            RandomListNode p2=p1.next;//p2为下一节点

            if(p1.random!=null)//p1的随机结点为null时，p1的next结点找不到，但p2应该为空

              p2.random=p1.random.next;

              p1=p2.next;

        }//随机值拷贝完成

        p1=head;

        RandomListNode newHead=head.next;

        while(p1!=null){

            RandomListNode p2=p1.next;

            p1.next=p2.next;

            if(p2.next!=null){

                p2.next=p2.next.next;

            }

            p1=p1.next;

      }//将链表拆开，返回新拷贝的链表

    return newHead;

    }   

}