本文共 3007 字，大约阅读时间需要 10 分钟。

题目描述

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

分析：

方法一 用HashMap保存random对应关系，第一遍复制链表，第二遍使用HashMap设置新链表的random对应关系。

import java.util.HashMap;public class Solution {    public RandomListNode Clone(RandomListNode pHead)    {        if(pHead==null)            return null;        RandomListNode head = pHead;        RandomListNode pre = new RandomListNode(0);                HashMap
   
     map = new HashMap
    
     ();        while(pHead!=null){            pre.next = new RandomListNode(pHead.label);            pre = pre.next;            map.put(pHead, pre);            pHead = pHead.next;        }        pHead = head;        while(pHead!=null){            RandomListNode copynode = map.get(pHead);            copynode.random = map.get(pHead.random);            pHead = pHead.next;        }        return map.get(head);    }}
    
   

看到讨论区一个大佬用到遍历HashMap的方法，有两种：

第一种: 

使用Entry,返回的是set,用itorator迭代。这种效率比较高，推荐使用！！

<<,>>

() Returns a  view of the mappings contained in this map.

Map map = new HashMap(); 

Iterator iter = map.entrySet().iterator();  while (iter.hasNext()) {      Map.Entry entry = (Map.Entry) iter.next();      Object key = entry.getKey();      Object val = entry.getValue();  }  效率高,以后一定要使用此种方式！ 记得import：链接：

import java.util.HashMap;

import java.util.Iterator;

import java.util.Map.Entry;

import java.util.Set;

对应本题中：

Set
   
    
     > set = map.entrySet();         Iterator
     
      
       > it = set.iterator();         while(it.hasNext()){            Entry
       
         next = it.next();                        next.getValue().random = map.get(next.getKey().random);        }
       
      
     
    
   

第二种:  Map map = new HashMap();  Iterator iter = map.keySet().iterator();  while (iter.hasNext()) {      Object key = iter.next();      Object val = map.get(key);  }  效率低,以后尽量少使用！

方法二

将新的复制节点放在旧节点之后，然后再次从头遍历，旧节点的random.next就是新节点的random.最后偶数位置的节点就是新的链表

1. 把复制的结点链接在原始链表的每一对应结点后面

       

    2. 把复制的结点的random指针指向被复制结点的random指针的下一个结点

    3. 拆分成两个链表，奇数位置为原链表，偶数位置为复制链表，注意复制链表的最后一个结点的next指针不能跟原链表指向同一个空结点None，next指针要重新赋值None(判定程序会认定你没有完成复制）

    

import java.util.HashMap;public class Solution {    public RandomListNode Clone(RandomListNode pHead)    {        if(pHead==null)            return null;        RandomListNode head = pHead;        while(head != null){            RandomListNode next = head.next;            RandomListNode copy = new RandomListNode(head.label);            head.next = copy;            copy.next = next;            head = next;        }        head = pHead;        while(head !=null){            head.next.random = head.random!=null?head.random.next:null;            head = head.next.next;        }        head = pHead;        RandomListNode clone = pHead.next;        RandomListNode node = clone;        while(node!=null){            head.next = node.next!=null? node.next:null;            node.next = node.next!=null? node.next.next:null;//z注意这两行不能写反            node = node.next;            head = head.next;        }        return clone;            }}

 

转载地址：http://uifni.baihongyu.com/