题目描述

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

解题思路

  1. 遍历该链表,复制每一个节点,插入到当前节点的后面.形成如下链表. 1->1’->2->2’….
  2. 将每个拷贝节点的随机指针域,指向原节点(即拷贝节点的上一个节点)的随即指针域指向(注意随机指针域可能为空)的下一个节点.即1的随机指针域指向3,则1’的随机指针域指向3的下一个指针3’.

  3. 拆分链表,返回1’->2’->3’…

    代码实现

    1. /*
    2. public class RandomListNode {
    3.  int label;
    4.  RandomListNode next = null;
    5.  RandomListNode random = null;
    7.  RandomListNode(int label) {
    8.      this.label = label;
    9.  }
    10. }
    11. */
    12. public class Solution {
    13.  public RandomListNode Clone(RandomListNode pHead)
    14.  {
    15.      if(pHead==null)return null;
    16.      RandomListNode runner=pHead;
    17.      RandomListNode copyCat=null;
    18.      //First round: make copy of each nodes
    19.      while(runner!=null){
    20.          copyCat=new RandomListNode(runner.label);
    21.          copyCat.next=runner.next;
    22.          runner.next=copyCat;
    23.          runner=copyCat.next;
    24.      }
    26.      //Second Round: assign random pointers for the copy nodes
    27.      runner=pHead;       
    28.      while(runner!=null){
    29.          copyCat=runner.next;
    30.          //notice random pointers could be null
    31.          copyCat.random=runner.random==null?null:runner.random.next;
    32.          runner=runner.next.next;
    33.      }
    35.      //Third round: restore the original list, and extract the copy list.
    36.      runner=pHead;
    37.      pHead=runner.next;
    38.      while(true){
    39.          copyCat=runner.next;
    40.          runner.next=copyCat.next;
    41.          runner=copyCat.next;
    42.          if(runner==null){
    43.              break;
    44.          }
    45.          else{
    46.             copyCat.next=runner.next;
    47.          }           
    48.      }
    49.      return pHead;
    50.  }
    51. }