左程云算法与数据结构课 https://www.bilibili.com/video/BV13g41157hK?p=2&spm_id_from=pageDriver
一种特殊的单链表节点描述如下
class Node { int value; Node next; Node rand; Node(int val) { value = val; } }
rand 指针是单链表节点结构中新增的指针,rand 可能指向链表中的任意一个位置,也可能指向 null。给定一个由 Node 节点类型组成的无环单链表的头节点 head,请实现一个函数完成链表的复制,并返回复制的新链表的头节点。要求时间复杂度O(N),空间复杂度O(1)。
设原链表如下
生成克隆节点并放在原节点的下一个位置。
一对一对地把节点拿出来把 rand 指针复制。例如把 1 和 1’ 节点拿出来,1 的 rand 指向 3,故 1‘ 的 rand 指向 3 的下一个节点,即 3’ 节点。
最后分裂成新老链表即可。
public class CopyListWithRandom { static class Node { int value; Node next; Node rand; Node(int val) { value = val; } } public static Node copyListWithRand(Node head) { if (head == null) { return null; } Node cur = head; Node next = null; //复制新节点放在老节点后面 while (cur != null) { next = cur.next; cur.next = new Node(cur.value); cur.next.next = next; cur = next; } //设置复制节点的 rand 指针 cur = head; Node curCopy = null; 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; while (cur != null) { next = cur.next.next; curCopy = cur.next; cur.next = next; curCopy.next = next != null ? next.next : null; cur = next; } return res; } }