【JAVA】2.输入一个复杂链表（每个节点中有节点值， 以及两个指针，一个指向下一个节点， 另一个特殊指针指向任意一个节点）， 返回结果为复制后复杂链表的head。 （注意，输出结果中请不要返回参数中

package 牛客网练习题;
//public class RandomListNode {
//	int label;
//	RandomListNode next = null;
//	RandomListNode random = null;
//
//	RandomListNode(int label) {
//		this.label = label;
//	}
//}

public class 输入一个复杂链表_返回结果为复制后复杂链表的head {
	public RandomListNode Clone(RandomListNode pHead) {
		// 判断p链表的头节点是否为空
		if (pHead == null)
			return null;
		// 初始化pCur为，原链表的头节点
		RandomListNode pCur = pHead;
		/**
		 * 1.复制next，如原来是A->B->C ，变成A->A'->B->B'->C->C'
		 */

		// 头节点不为空时，
		while (pCur != null) {
			// 创建一个node对象，作为pCur的标记链表
			RandomListNode node = new RandomListNode(pCur.label);
			// 进行节点复制
			node.next = pCur.next;
			pCur.next = node;
			pCur = node.next;
		}

		pCur = pHead;
		/**
		 * 2.复制random，pCur是原来链表的结点 ，pCur.next是复制pCur的结点
		 */

		// 当头节点的特殊指针指向的随机节点不为空时
		while (pCur != null) {
			// 当原链表头节点的特殊指针指向的随机节点不为空时
			if (pCur.random != null)

				// 将头节点的特殊指针所指向的随机节点的下一个节点，
				// 赋给原链表下一个节点的特殊指针所指向的随机节点的下一个节点。
				pCur.next.random = pCur.random.next;
			// 将头节点的next-->next节点赋给头节点
			pCur = pCur.next.next;
		}

		// 初始化head节点为，原理链表的头节点的下一个节点
		RandomListNode head = pHead.next;
		RandomListNode cur = head;

		pCur = pHead;

		/**
		 * 3.拆分链表
		 */

		// 当头节点的特殊指针指向的随机节点不为空时
		while (pCur != null) {
			// 将头节点的next-->next节点赋给头节点的下一个节点
			pCur.next = pCur.next.next;
			// 当 pHead.next节点的下一个节点不为空时
			if (cur.next != null)
				cur.next = cur.next.next;
			cur = cur.next;
			pCur = pCur.next;
		}
		return head;
	}
}