[名企面试知识点][Java]复杂链表的复制
发布于 2017-03-08 13:32 1236 次浏览 0 赞 来自 笔试面试  

题目描述

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点)。

输入描述

一个复杂链表头结点

输出描述

该链表的复制链表头结点

题目分析

  节点描述:

public class RandomListNode {
   int label;
   RandomListNode next = null;
   RandomListNode random = null;

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

解法一 运行时间:36ms 占用内存:566k

public class Solution {
   public RandomListNode Clone(RandomListNode pHead)
   {  
       if(pHead==null) return pHead;
       RandomListNode copyHead = new RandomListNode(pHead.label);
       copyHead.random = pHead.random;        
       copyHead.next = Clone(pHead.next);

       return copyHead;
   }
}

  用递归的方式复制每一个节点。

解法二  运行时间:31ms 占用内存:692k 

public class Solution {
   public RandomListNode Clone(RandomListNode pHead)
   {  
       if(pHead==null) return pHead;
       //拷贝新链表头节点
       RandomListNode copyHead = CopyNode(pHead);
       //新链表指针节点
       RandomListNode copyPoint = copyHead;
       while(pHead.next!=null){
           //把拷贝的节点加到新链表
           copyPoint.next = CopyNode(pHead.next);
           //两个链表指针向后移动
           copyPoint = copyPoint.next;
           pHead = pHead.next;
       }
       return copyHead;
   }
   //拷贝节点函数
  public RandomListNode CopyNode(RandomListNode node){
      RandomListNode temp = new RandomListNode(node.label);
      temp.next = node.next;
      temp.random = node.random;
      return temp;
  }
}

 循环遍历链表把每个节点拷贝到新链表中。

添加回复
回到顶部