【算法】复制含有随机指针节点的链表---MapleYe

题目

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

public static class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; } }

next指针和正常单链表中next指针的意义 一 样，都指向下一个节点， rand指针是Node类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向null。 给定一个由 Node节点类型组成的无环单链表的头节点head， 请实现一个 函数完成 这个链表中所有结构的复制，并返回复制的新链表的头节点。

进阶要求

不使用额外的数据结构，只用有限几个变量， 且在时间复杂度为 O(N) 内完成原问题要实现的函数

基础解法思路

1、使用hashMap，以Node为键，给每个Node创建一个副本 2、最后根据原来链表的next指针和rand指针，重连hashMap中的节点

算法实现 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; // 根据原来链表的next指针和rand指针，重连hashMap中的节点 while(cur != null) { map.get(cur).next = map.get(cur.next); map.get(cur).rand = map.get(cur.rand); cur = cur.next; } return map.get(head); }进阶解法思路

1、拷贝节点，例如对于 1->2->3->4 我们插入每个节点的后面插入其copy节点，使之为 1->1'->2->2'->3->3'->4->4' 2、那么我们通过找到源节点，即可找到其copy节点的位置（源节点.next），相当于哈希表的作用 3、最后根据原链表的rand关系，链接copy节点的rand指针 4、最后将链表拆分为原链表和copy链表

算法实现 public static Node copyListWithRand2(Node node) { if(node == null) { return node; } Node cur = node; while(cur != null) { Node next = cur.next; // 拷贝节点，并插入其后 Node copy = new Node(cur.value); copy.next = cur.next; cur.next = copy; cur = next; } // 连接rand指针 cur = node; Node copyNode = cur.next; while(cur != null) { if(cur.rand != null) { // 由于cur.rand.next就是cur.rand的拷贝节点 // 因此copyNode.rand指针，指向cur.rand.next copyNode.rand = cur.rand.next; } cur = cur.next.next; if(cur != null) { copyNode = cur.next; } } // 拆分链接 cur = node; copyNode = cur.next; Node copyHead = cur.next; while(cur != null) { // 保存next指针 Node tmp = copyNode.next; cur.next = copyNode.next; copyNode.next = cur.next; cur = tmp; if(cur != null) { copyNode = cur.next; } } return copyHead; } ---来自腾讯云社区的---MapleYe