题目：

一种特殊的单链表节点类描述如下:

class Node {

        int value;

        Node next;

        Node rand;

        Node(int val) {value = val}

}

rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点（包括自己），也可能指向null.

给定一个由Node节点类型组成的无环单链表的头结点head，请实现一个函数完成复制这个链表，并返回新链表的头结点。

要求：时间复杂度O(N)，额外空间复杂度O(1)

思路：这个题仍然有两种解法：利用额外容器或者使用有限几个变量，具体思路：

（1）使用额外的容器，使用一个HashMap，把当前链表的每一个Node作为key装入HashMap，value是它的拷贝节点，都装完之后依次取出每一个Node，把value（拷贝节点）的next和random分别指向HashMap中取出的以当前节点的next和random为key的拷贝节点，没有

（2）不使用额外的容器，只使用有限几个变量，先遍历链表，依次拷贝Node然后把拷贝节点放在当前当前节点和原来的next中间。 然后依次遍历链表，设置各个拷贝节点的random指针指向。最后把两个链表进行拆分.

第一种方法面试没有分且笔试的空间复杂度为O(N)，笔试也过不了，这里我们不做介绍，有兴趣的可以自己写写玩。

第二种方法的拆分示意图：

对应的代码如下：

package dataStructure.linkedList.practice;import dataStructure.linkedList.ListNodeWithRandom;public class CopyLinkedListWithRandom {public static ListNodeWithRandom copyLinkedList(ListNodeWithRandom head) {if(head == null) return head;ListNodeWithRandom cur = head;ListNodeWithRandom next = null;//把每个节点复制一个放在当前节点和当前节点的next之间,最后一个copy放在当前节点和null之间//例如1->2->3变成1->11->2->22->3->33while(cur != null) {next = cur.next;cur.next = new ListNodeWithRandom(cur.val, cur.name+"'");cur.next.next = next;cur = next;}cur = head;//设置random指针while(cur != null) {//取到当前Node的random指针ListNodeWithRandom random = cur.random;//当前random如果为空，那拷贝节点的random也应该为空//如果当前random不为空，则random的下一个(原链表中random的拷贝)就是拷贝节点的randomcur.next.random = random == null? null : random.next;//cur.next.next是原链表中cur的下一个节点cur = cur.next.next;}//分离原链表和拷贝链表//1->11->2->22->3->33 分离为1->2->3和11->22->33cur = head;ListNodeWithRandom newHead = null;while(cur != null) {//取到cur的拷贝节点ListNodeWithRandom curCopy = cur.next;//如果当前节点是头节点，则它的拷贝就是新链表的头if(newHead == null) {newHead = curCopy;}//cur的下一个节点就是curCopy的下一个节点cur.next = curCopy.next;//curCopy的next取决于cur.next是否为空，如果为空，则它的next也应该为空//如果不为空，根据规律我们应该取cur.next的下一个节点（cur.next的拷贝）curCopy.next = cur.next == null? null : cur.next.next;//这个时候cur.next已经是cur的原链表的下一个节点了cur = cur.next;}return newHead;}public static void main(String[] args) {ListNodeWithRandom n1 = new ListNodeWithRandom(1, "1");ListNodeWithRandom n2 = new ListNodeWithRandom(2,"2");ListNodeWithRandom n3 = new ListNodeWithRandom(3, "3");n1.next = n2;n2.next = n3;n1.random = n3;n2.random = n1;n3.random = n2;ListNodeWithRandom newHead = copyLinkedList(n1);while(newHead != null) {if(newHead.next != null) {System.out.print(newHead + " ->");} else {System.out.print(newHead);}newHead = newHead.next;}}
}

运行结果：

{val=1, random=3', name='1''} ->{val=2, random=1', name='2''} ->{val=3, random=2', name='3''}

粗略代码，难免出错，欢迎批评指正