1. Title Description

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.

public class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; }}Copy the code

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 = [] Output: [] Description: The given linked list is null (null pointer), so null is returned.Copy the code

2. How to solve the problem

Hash table

Algorithm that

Based on the query characteristics of hash table, consider the key-value pair mapping relationship between the original linked list node and the corresponding node of the new linked list, and iterate the next and random reference points of each node of the new linked list.

Algorithm process

1. If head is empty, null is returned.

2. Initialize dic, node cur points to the head node;

3, Copy linked list:

  1. Create new nodes and add key-value pairs (old CUR, new CUR) to DIC;
  2. Cur traverses to the next node of the original linked list;

4, build a new list of references to:

  1. Next and random references to build new nodes point to;
  2. Cur traverses to the next node of the original linked list;

Dic [cur]; dic[cur];

Code implementation

public Node copyRandomList(Node head) {
    if(head == null) {return head;
    }
    Map<Node,Node> map = new HashMap<>();
    Node cur = head;
    while(cur ! =null){
        Node node = new Node(cur.val);
        map.put(cur,node);
        cur = cur.next;
    }
    cur = head;
    while(cur! =null){
        map.get(cur).next = map.get(cur.next);
        map.get(cur).random = map.get(cur.random);
        cur = cur.next;
    }
    return map.get(head);
}
Copy the code

Complexity analysis

  • Time complexity O(N) : The time complexity of traversing the linked list is O(N) for two rounds.
  • Spatial complexity O(N) : The dic hash table uses additional space of linear size.

Two, splicing + split

Algorithm that

Copy any node N of the original linked list and create a new node N’, then link N’ to the end of N. Assume that the random of N on the original linked list points to node S, then the corresponding copied N’ is the node to which N’s next points, and S’ is also the node to which S’s next points. If radom points to null, random of S’ points to null

Algorithm process

1. Copy each node and join it into a new linked list;

2. Construct the random pointing of each node of the new linked list;

The solid line represents the pointer to next, and the dotted line represents the pointer to Random.

3. Split the original/new linked list. Split the long linked list into two linked lists.

Code implementation

public Node copyRandomList(Node head) { if(head == null){ return head; } //1, Node cur = head; while(cur! =null){ Node node = new Node(cur.val); node.next = cur.next; cur.next = node; cur = cur.next.next; } //2. while(cur! =null){ Node pClone = cur.next; if(cur.random! =null){ pClone.random = cur.random.next; } cur = pClone.next; } //3, cur = head. Next; Node pre = head; Node res = head.next; while(cur.next! =null){ pre.next = cur.next; cur.next = cur.next.next; pre = pre.next; cur = cur.next; } // Next = null; return res; }Copy the code

Complexity analysis

  • Time complexity: O(N), traversing the list three times, time complexity is O(N).
  • Space complexity: O(1), node reference variables use extra space of constant size.