复杂链表的复制—

题目描述：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

数据结构：

public class RandomListNode {
    int label; 数据域
    RandomListNode next = null;    指向下一个结点
    RandomListNode random = null; 指向任意一个节点

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

解题思路：

1、遍历链表，复制链表中的每个结点，并将复制的结点插入到该结点的后面。例如，原链表为A->B->C, 遍历完毕后，链表变为A->A'->B->B'->C->C'，其中A‘，B'，C'是结点A，B，C的复制结点。

看图中，蓝色箭头为next指针：

复制结点后：

2、为复制结点的random指针赋值

如果原结点的random指针指向的是结点B，那么将复制结点的random指针指向结点B的复制结点B'。

图中黑色箭头为random指针：

复制结点的random指针赋值后：

3、将链表的原始结点与复制结点分割至两个链表，使原始结点构成一个链表，复制结点构成一个链表。

代码实现：

1、复制结点

 //1.加入copy结点

public void copyNodes(RandomListNode pHead){

        RandomListNode walkNode=pHead;

         while(walkNode!=null){

             RandomListNode cloneNode=new RandomListNode(walkNode.label);

             cloneNode.next=walkNode.next;

             walkNode.next=cloneNode;

             walkNode=cloneNode.next;

         }

}

2、为复制结点的random指针域赋值

//2.为新copy结点的random域指定值

    public void initRandom(RandomListNode pHead){

         RandomListNode walkNode=pHead;

         RandomListNode cwalkNode=pHead;

         while(walkNode!=null){

             cwalkNode=walkNode.next;

             if(walkNode.random!=null){

                 cwalkNode.random=walkNode.random.next;

             }

             walkNode=cwalkNode.next;

         }

}

3、将结点和复制结点分为两个链表

//3.将链表和其copy版本分为两个链表

     public RandomListNode split2list(RandomListNode pHead){

         RandomListNode cpHead=pHead.next;

         RandomListNode walkNode=pHead;

         RandomListNode cwalkNode=cpHead;

         while(walkNode!=null){

             walkNode.next=cwalkNode.next;

             walkNode=walkNode.next;

             if(walkNode==null){

                 cwalkNode.next=null;

             }

             else{

                 cwalkNode.next=walkNode.next;

                 cwalkNode=cwalkNode.next;

             }

         }

         return cpHead;

     }

4、总的调用函数

public RandomListNode Clone(RandomListNode pHead)

{

         if(pHead==null){

             return null;

         }

         copyNodes(pHead);

         initRandom(pHead);

         return split2list(pHead);

 }

全部代码

 class RandomListNode {

     int label;

     RandomListNode next = null;

     RandomListNode random = null;

     RandomListNode(int label) {

         this.label = label;

     }

 }

 public class copyList {

      //1.加入copy结点

     public void copyNodes(RandomListNode pHead){

         RandomListNode walkNode=pHead;

          while(walkNode!=null){

              RandomListNode cloneNode=new RandomListNode(walkNode.label);

              cloneNode.next=walkNode.next;

              walkNode.next=cloneNode;

              walkNode=cloneNode.next;

          }

      }

     //2.为新copy结点的random域指定值

      public void initRandom(RandomListNode pHead){

          RandomListNode walkNode=pHead;

          RandomListNode cwalkNode=pHead;

          while(walkNode!=null){

              cwalkNode=walkNode.next;

              if(walkNode.random!=null){

                  cwalkNode.random=walkNode.random.next;

              }

              walkNode=cwalkNode.next;

          }

      }

     //3.将链表和其copy版本分为两个链表

      public RandomListNode split2list(RandomListNode pHead){

          RandomListNode cpHead=pHead.next;

          RandomListNode walkNode=pHead;

          RandomListNode cwalkNode=cpHead;

          while(walkNode!=null){

              walkNode.next=cwalkNode.next;

              walkNode=walkNode.next;

              if(walkNode==null){

                  cwalkNode.next=null;

              }

              else{

                  cwalkNode.next=walkNode.next;

                  cwalkNode=cwalkNode.next;

              }

          }

          return cpHead;

      }

      public RandomListNode Clone(RandomListNode pHead)

      {

          if(pHead==null){

              return null;

          }

          copyNodes(pHead);

          initRandom(pHead);

          return split2list(pHead);

      }

      public static void main(String[]args){

             RandomListNode head = new RandomListNode(1);

             RandomListNode node2 = new RandomListNode(2);

             RandomListNode node3 = new RandomListNode(3);

             RandomListNode node4 = new RandomListNode(4);

             RandomListNode node5 = new RandomListNode(5);

             head.next = node2;

             node2.next = node3;

             node3.next = node4;

             node4.next = node5;

             head.random = node3;

             node2.random = node5;

             node4.random = node2;

             copyList s = new copyList();

             RandomListNode copyList=s.Clone(head);

             System.out.print(copyList.label + " ");

 //            while (copyList != null)

 //            {

 //                System.out.print(copyList.label + " ")

 //                copyList = copyList.next;

 //            }

      }

 }

巴特西

复杂链表的复制——牛客offer

最新文章

热门文章