【题解】剑指Offer-34 复杂链表的复制
复杂链表的复制(剑指Offer-34)
题面
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
示例
示例 1:
1 | 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] |
示例 2:
1 | 输入:head = [[1,1],[2,1]] |
示例 3:
1 | 输入:head = [[3,null],[3,0],[3,null]] |
示例 4:
1 | 输入:head = [] |
限制
1 | -10000 <= Node.val <= 10000 |
思路
复制各节点,构建拼接链表: 设原链表为
node1 → node2 → ⋯
,构建的拼接链表如下所示:node1 → node1new → node2 → node2new → ⋯
构建新链表各节点的 random 指向: 当访问原节点 cur 的随机指向节点 cur.random 时,对应新节点 cur.next 的随机指向节点为 cur.random.next 。
拆分原 / 新链表: 设置 pre / cur 分别指向原 / 新链表头节点,遍历执行 pre.next = pre.next.next 和 cur.next = cur.next.next 将两链表拆分开。
返回新链表的头节点 res 即可。
代码
1 | /* |