Example Analysis of Java complex linked list
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.
