JZ35 复杂链表的复制

JZ35 复杂链表的复制

有磕绊有学习有成长，才有开心。这道题感觉还是有学习到的。学习到的原因是有的代码实在是太长了。两害取其轻，挑个短点的学个知识点吧~

描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

思路

与其说思路，不如说简单介绍一下我的代码的优势和我的思考突破点。优点的话就是构建了完整的调试代码，你可以在本地一点点调试。

突破点在与HashMap，其实一开始看到map.get(cur).next = map.get(cur.next);这句及后面那句是有点蒙的，然后我又去回顾了HashMap的结构。图片不是我画的啦，可以看这个连接里的。图片的意思是hashmap是一种由数组和链表组成的结构。key作为数组的索引，通过key找到完整的链表。当然你也可以将链表替换为其他结构比如本文中的节点（对象）

代码

package tenDay;

import java.util.HashMap;

public class JZ35 {
	public RandomListNode Clone(RandomListNode pHead) {
		HashMap map = new HashMap();
        RandomListNode cur = pHead;
        //遍历原有节点
        while(cur!=null) {
        	//设置新节点
        	RandomListNode node = new RandomListNode(cur.label);
            //将新节点和老节点按对应关系放入hash表 
        	map.put(cur, node);
        	cur = cur.next;
        }
        //将指针重新移至头结点
        cur = pHead;
        while (cur !=null) {
        	//新节点的下一个节点是哪里：当然和老节点的下一个节点在一个单元里
			map.get(cur).next = map.get(cur.next);
			map.get(cur).random = map.get(cur.random);
			cur=cur.next;
		}
        //同理新节点的头结点和老节点的头结点在一个单元里
        return map.get(pHead);
    }
	public static void main(String[] args) {
		RandomListNode node1 = new RandomListNode(1);
		RandomListNode node2 = new RandomListNode(2);
		RandomListNode node3 = new RandomListNode(3);
		RandomListNode node4 = new RandomListNode(4);
		RandomListNode node5 = new RandomListNode(5);
		node1.next = node2;
		node1.random = node3;
		node2.next = node3;
		node2.random = node4;
		node3.next = node4;
		node3.random = null;
		node4.next = node5;
		node4.random = node2;
		node5.random = null;
		JZ35 jz35 = new JZ35();
		jz35.Clone(node1);
	}
}

package tenDay;

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

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