Java 复杂链表
Fly upward 人气:01.题目
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
2.解法
2.1 拼接+拆分
首先我们逐个将节点复制并且和原来的链表连起来得新链表;
然后再构建新链表的random 指向。当访问原节点 cur
的随机指向节点 cur.random
时,对应新节点 cur.next
的随机指向节点为 cur.random.next
将得到的新链表之间的复制节点拆分出来连成一个复制链表,拆分成原链表和复制链表。
链表图
复制节点
将复制节点的random.next 连接起来
拆分成两个链表
3.代码
class Solution { public Node copyRandomList(Node head) { if(head == null) { return null; } //1.复制各个链表,并连接 Node cur = head; while (cur != null) { //复制 Node prev = new Node(cur.val); prev.next = cur.next; //连接 cur.next = prev; //往后走 cur = prev.next; } //2.构建各新节点的random 指向 cur = head; while (cur != null) { if (cur.random != null) { cur.next.random = cur.random.next; } cur = cur.next.next; } //3.拆分复制的链表 cur = head.next; Node node = head; Node nodeNext = head.next; while (cur.next != null) { node.next = node.next.next; cur.next = cur.next.next; node = node.next; cur = cur.next; } node.next = null;//尾节点 return nodeNext;//返回新链表的头结点 } }
加载全部内容