Java复杂链表的复制详解

Java复杂链表的复制详解

目录1.题目2.解法2.1 拼接+拆分3.代码

1.题目

请实现 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 http://Solution {

public Node copyRandomList(Node head) {

if(head == null) {

return null;

}

//1.复制各个链表，并连接

Node cur = head;

while (cur != null) {

//复制

Node prev = new Node(cur.val);

prehttp://v.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;//返回新链表的头结点

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。