每天一道算法题——复杂链表的复制

前言：
今天这个题有些没想到，精神不怎么好。

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

测试用例:
{1,2,3,4,5,3,5,#,2,#}
对应输出应该为:
{1,2,3,4,5,3,5,#,2,#}
分析：

首先对这个复杂链表进行分析，说这个链表复杂只是多出了一个称为random的特殊指针，它指向链表中任意一项。
首先想到的是复制原始链表上的每一个结点，并通过pNext连接起来；然后再设置每个结点的pSibling指针。但是这样有些暴力，因为若原链表中某个结点p的random指针指向结点q,那么就需要从头到尾遍历查找结点q。这样的算法复杂度为O(n^2)，理论上应该有优化的可能。
方法一：在思考良久后采用哈希表将原始链表和复制链表对应起来，这样就会使查找random的时间从O(n)降到O(1)这样算法复杂度也会降到O(n)，算是以空间换时间吧。
复制原链表上的每个结点p创建t，然后把这些创建出来的结点用link连接起来。同时把<p,t>的配对信息方法一个哈希表中；然后设置复制链表中的每个结点的random指针，如果原链表中结点p的random指向结点q，那么在复制链表中，对应的t应该指向q’。以本体为key来搭建复制体的random链接.
**方法二：**这个算法是在网上找到的一个非常好的解法。
第一步：根据原始链表的每个结点N创建对应的N’，然后将N‘通过pNext接到N的后面；

第二步：设置复制出来的结点的pSibling。假设原始链表上的N的pSibling指向结点S，那么其对应复制出来的N’是N->pNext指向的结点，同样S’也是结点S->pNext指向的结点。

第三步：把长链表拆分成两个链表，把奇数位置的结点用pNext连接起来的就是原始链表，把偶数位置的结点通过pNext连接起来的就是复制链表。

源码：
方法一——哈希映射：

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;

public class Test1 {
	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)
	    {
	    	HashMap<RandomListNode, RandomListNode> hashMap = new HashMap<RandomListNode,RandomListNode>();
	    	RandomListNode p = pHead;
	    	RandomListNode link = new RandomListNode(0);
	    	while (p!=null) {
				RandomListNode cloneP = new RandomListNode(p.label);
				hashMap.put(p, cloneP);
				p = p.next;
				link.next = cloneP;
				link = cloneP;
			}
	    	Set<Entry<RandomListNode, RandomListNode>> set = hashMap.entrySet();
	    	Iterator<Entry<RandomListNode, RandomListNode>> iterator = set.iterator();
	    	while (iterator.hasNext()) {
	    		Entry<RandomListNode, RandomListNode> next = iterator.next();
	    		next.getValue().random = hashMap.get(next.getKey().random);
			}
	    	return hashMap.get(pHead);
	    }
	}
}

循环：

import java.util.ArrayList;
import java.util.Stack;

public class Test1 {
	public class Solution {
	    public boolean VerifySquenceOfBST(int [] sequence) {
	        int size = sequence.length;
	        if (size==0) {
				return false;
			}
	        int i = 0;
	        while(--size!=0){
	        	while(sequence[i++]<sequence[size]);
	        	while(i<size&&sequence[i++]>sequence[size]);
	        	
	        	if (i<size) {
					return false;
				}
	        	i = 0;
	        }
	        return true;
	    }
	}
}

运行测试：

递归测试：运行时间：19ms 占用内存：9544k
循环测试：运行时间：16ms 占用内存：8592k

总结：
此题重点考验了对二分查找树（Binary Search Tree）的结构理解。只要晓得了BST的后序序列规则，使用递归的思想很容易就能得到一个解，但是递归效率要低于循环，所以可以想办法将递归转化为循环即可。