复杂链表的复制.md

题目描述

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

##输入描述

一个复杂链表头结点

##输出描述

该链表的复制链表头结点

##题目分析

　　节点描述：

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;
   }
}

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