题目
一种特殊的单链表节点类描述如下：
class Node { int value; Node next; Node rand; Node(int val) { value = val ; } } 复制代码
rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
【要求】时间复杂度O(N)，额外空间复杂度0(1)
法一：Hash表拷贝链表
笔试中使用能帮助尽快解题
思路
- 遍历原链表，采用一个Hash表，其key值放老结点的内存地址，value放入从老结点中复制得来的新结点内存地址，当结点遍历完毕后，所有的新旧结点均拷贝完毕；
- 再次遍历原链表，每遍历一个结点，就得出他的rand和next指针，然后因为next指针和rand指针都是作为Hash表key存在，所以可以依据这个next和rand指针经由hash函数得出其对应新结点的所在地址（假设为N和R），再根据当前结点和哈希函数，得出当前结点的新结点，然后再设置新结点的next和rand指针分别指向N和R
复杂度
空间复杂度为O(N)，时间复杂度为O(N)
public static Node copyListWithRand1(Node head){ HashMap<Node, Node> map = new HashMap<Node, Node>(); Node cur = head; while(cur != null){ map.put(cur, new Node(cur.value)); cur = cur.next; } cur = head; while(cur != null){ // cur 老 // map.get(cur) 新 map.get(cur).next = map.get(cur.next); map.get(cur).rand = map.get(cur.rand); cur = cur.next; } return map.get(head); } 复制代码
法二：利用新旧节点之间的位置关系
思路
利用新旧节点之间的位置关系而省略了方法一中的额外的hash表空间
步骤
- 生成克隆节点：把克隆节点就直接放在老链表的下一个，然后克隆节点去串上老链表的下一个（克隆节点插在当前所遍历节点与下一个要遍历节点之间），遍历完成之后，老节点的rand指向保持不变，新节点的rand无指向，如下图：
网络异常，图片无法展示|
- 设置克隆节点的rand：遍历含有新老节点的链表，每次遍历到老节点时，能获取到rand，此时直接设置克隆节点的rand
- 分离新老链表
复杂度
空间复杂度为O(1)，时间复杂度为O(N)
public static Node copyListWithRand2(Node head){ if(head == null){ return null; } Node cur = head; Node next = null; // copy node and link to every node // 1->2 // 1->1'->2 while(cur != null){ next = cur.next; cur.next = new Node(cur.value); cur.next.next = next; cur = next; } cur = head; Node curCopy = null; // set copy node rand // 1->1'->2->2' while(cur != null){ next = cur.next.next; curCopy = cur.next; curCopy.rand = cur.rand != null ? cur.rand.next : null; cur = next; } Node res = head.next; cur = head; // split while(cur != null){ next = cur.next.next; curCopy = cur.next; cur.next = next; curCopy.next = next != null ? next.next : null; cur = next; } return res } 复制代码
