转载

复杂链表的复制

复杂链表的复制

  • 题目

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

  • 思想

    由于链表节点必须重新分配,普通的遍历方法相形见绌,所以有如下方法。

    图片

  • 代码:

    /* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */
    public class Solution {
      public RandomListNode Clone(RandomListNode pHead)
      {
          RandomListNode temp = pHead;
          if(pHead == null) return null;
          while(temp != null) {
              RandomListNode copy = new RandomListNode(temp.label);
              copy.next = temp.next;
              temp.next = copy;
              temp = copy.next;
          }
    
    
          temp = pHead;
    
          while(temp != null) {
              if(temp.random != null) {
                   temp.next.random = temp.random.next;
              }
              temp = temp.next.next;
          }
    
            RandomListNode pCloneHead = pHead.next;
          RandomListNode tmp;
          RandomListNode currNode = pHead;
          while(currNode.next != null){
              tmp = currNode.next;
              currNode.next =tmp.next;
              currNode = tmp;
          }
          return pCloneHead;
      }
    }

    ?

    ?

正文到此结束
本文目录