[B] [C] [D]

Implement the function copyRandomList to copy a complex linked list. In complex linked lists, each node has a next pointer to the next node and a random pointer to any node in the list, or null.

Example 1:

Input: the head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] output: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]Copy the code

Example 2:

Input: head = [1,1],[2,1]] output: [[1,1],[2,1]]Copy the code

Example 3:

Input: the head = [[3, null], [3, 0], [3, null]] output: [[3, null], [3, 0], [3, null]]Copy the code

Example 4:

Input: head = [] Output: [] Description: The given linked list is null (null pointer), so null is returned.Copy the code

Tip:

  • -10000 <= Node.val <= 10000
  • Node.randomIs null or points to a node in the linked list.
  • The number of nodes does not exceed 1000.

Attention: leetcode-cn.com/problems/co…

Copying an ordinary linked list is very simple. The difficulty of this problem is that each node of the copied linked list has a random pointer that points to any node in the list or null

How do you copy the original list in this case?

The solution is as follows:

The answer to this question is as follows:

  1. The first special judgment is if the passed linked list isnullTo return tonull
  2. Copy a new node after each node of the original linked list, of the new nodevalOf the node being copiedval
  3. Will copy the node’srandomPointer to the copied linked list noderandomPointer to thenext, if the node is copiedrandomPointer tonullIs copied to the noderandomThe pointer also points tonull
  4. Split the replicated node from the original linked list into a separate linked list, that is, the copied linked list
  5. Return the head node of the copied list

The overall process is as follows:

The code is as follows:

Var copyRandomList = function(head) {if(head === null) return null; let pre = head,next = pre.next; While (pre){pre.next = new Node(pre.val); pre.next.next = next; pre = next; next = pre? pre.next:null; } // handle random pre = head,next = pre-.next; while(next){ next.random = pre.random? pre.random.next:null; pre = next.next; next = pre? pre.next:null; } // Get the head of the result list const res = head.next; // Start = head,next = pre.next; while(next){ pre.next = next.next; pre = pre.next; next.next = pre? pre.next:null; next = next.next } return res; };Copy the code

At this point we have completed the copy of leetcode- finger offer- complex linked list

If you have any questions or suggestions, please leave a comment!