Shulou(Shulou.com)06/01 Report--

This article will explain in detail the example analysis of the Java complex linked list. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

1. Title

Please implement the copyRandomList function to copy a complex linked list. In a complex linked list, each node not only has a next pointer to the next node, but also has an random pointer to any node in the linked list or null.

Topic source: LeetCode

Link: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

two。 Solution 2.1 splicing + splitting

First, we copy the nodes one by one and connect them to the original linked list to get a new linked list.

Then build the random point of the new linked list. When the random pointing node cur.random of the original node cur is accessed, the random pointing node corresponding to the new node cur.next is cur.random.next.

Split the replication nodes between the new linked lists into a copy linked list, and split it into the original linked list and the copy linked list.

Linked list diagram

Copy node

Connect the random.next of the replication node

Split into two linked lists

3. The code class Solution {public Node copyRandomList (Node head) {if (head = = null) {return null;} / / 1. Copy the linked lists and connect Node cur = head; while (cur! = null) {/ / copy Node prev = new Node (cur.val); prev.next = cur.next; / / connect cur.next = prev; / / go back to cur = prev.next;} / / 2. The random that builds each new node points to cur = head; while (cur! = null) {if (cur.random! = null) {cur.next.random = cur.random.next;} cur = cur.next.next;} / / 3. Split the copied linked list 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 / / tail node return nodeNext;// returns the header node of the new linked list}}

This is the end of this article on "sample analysis of Java complex linked lists". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it out for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.