题目：
请实现一个cloneNode方法，复制一个复杂链表。
在复杂链表中，每个结点除了有一个next指针指向下一个结点之外，还有一个random指向链表中的任意结点或者NULL。
结点的定义如下：
public static class ListNode {
int val;
ListNode next;
ListNode random;
ListNode(int x) {
val = x;
}
}
思路：
方法1：
复制原始链表上的每一个结点，并通过next连接起来；然后再设置每个结点的random指针。
假设原始链表中某个结点N的random指针指向结点S,那么就需要从头到尾遍历查找结点S，如果从原始链表的头指针开始，经过m步之后达到结点S，那么在复制链表中的结点N'的random指针指向的结点也是距离复制链表s步的结点。通过这种办法就可以为复制链表上的每个结点设置random指针。
时间复杂度：O(N^2)
方法2：
方法1是通过链表查找来得到random指针所指向的结点，实际上我们可以通过空间换取时间，将原始链表和复制链表的结点通过哈希表对应起来，这样查找的时间就从O(N)变为O(1)。具体如下：
复制原始链表上的每个结点N创建N'，然后把这些创建出来的结点用pNext连接起来。同时把<N,N'>的配对信息方法一个哈希表中；然后设置复制链表中的每个结点的random指针，如果原始链表中结点N的random指向结点S，那么在复制链表中，对应的N'应该指向S'。
时间复杂度：O(N)
根据方法2，我们可以写出代码：
private static ListNode cloneNode(ListNode head2) {
if (head2 == null) {
return null;
}
Map<ListNode, ListNode> map1 = new HashMap<>();
ListNode newHead = new ListNode(head2.val);
map1.put(head2, newHead);
ListNode head = newHead;
// 复制节点和next指针
for (ListNode cur = head2.next; cur != null; cur = cur.next) {
head.next = new ListNode(cur.val);
head = head.next;
map1.put(cur, head);
}
head = newHead;
// 复制random节点
ListNode ranNode = null;
for (ListNode cur = head2; cur != null; cur = cur.next) {
ranNode = map1.get(cur.random);
head.random = ranNode;
head = head.next;
}
return newHead;
}
方法3：
在不使用辅助空间的情况下实现O(N)的时间效率。
第一步：根据原始链表的每个结点N创建对应的N'，然后将N‘通过next接到N的后面；
第二步：设置复制出来的结点的random。假设原始链表上的N的random指向结点S，那么其对应复制出来的N'是N->pNext指向的结点，同样S'也是结点S->next指向的结点。
第三步：把长链表拆分成两个链表，把奇数位置的结点用next连接起来的就是原始链表，把偶数位置的结点通过next连接起来的就是复制链表。
如图：
根据方法3，我们可以写出代码：
// 不要额外空间的时间复杂度为O(N)
private static ListNode cloneNode2(ListNode head2) {
if (head2 == null) {
return null;
}
// 复制节点和next指针
ListNode cur = head2;
while (cur != null) {
ListNode prev = cur.next;
ListNode clone = new ListNode(cur.val);
cur.next = clone;
cur.next.next = prev;
cur = prev;
}
ListNode old = head2;
ListNode clone = old.next;
while (clone != null) {
if (old.random != null) {
clone.random = old.random.next;
}
old = clone.next;
if (old != null) {
clone = old.next;
} else {
break;
}
}
ListNode res = oddEvenList(head2);
return res;
}
上面的代码可以得到图4.10的结构，而这个时候我们希望把链表分开，老的节点和复制的节点各分为一边，于是乎，出现了奇偶节点的变换（LeetCode328题）：
public static ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode oddNode = head;
ListNode evenNode = head.next;
ListNode cur = evenNode.next;
ListNode evenTemp = evenNode;
int index = 3;
while (cur != null) {
if (index % 2 == 0) {
evenNode.next = cur;
evenNode = evenNode.next;
} else {
oddNode.next = cur;
oddNode = oddNode.next;
}
cur = cur.next;
index++;
}
evenNode.next = null;
return evenTemp;
}
返回的evenTemp节点就是我们复制链表的第一个节点！