Subject analysis

  • The original topic content is too long, we simply analyze the main topic
  • There is a linked list of length N, and each node has a pointer to next and a pointer to random
  • We need to copy the list, and the new list must have the same pointer as the original list

The sample

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

Hash table implementation

The main idea

  1. Iterate through the linked list, copy each node to form a new linked list, and add the original list node and corresponding new node to the Map
  2. Then iterate over the original list again if the random pointer to the original list node is not null
  3. Gets the new list node corresponding to the random pointer of the original list node from Map
  4. Points a random pointer to a new linked list node to the corresponding node

Code implementation

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

Space optimization

The main idea

  1. Create a virtual header and point to the head
  2. Iterate through the list and copy the nodes, each pointing to the copied node
  3. For example, 1 -> 2 -> 3 becomes Dummty -> 1 -> 1 -> 2 -> 2 -> 3 -> 3
  4. Walk through the list again, and head. Next is the copied new node
  5. So head.next-random = head.random.next
  6. Finally split the linked list

Code implementation

public Node copyRandomList(Node head) { if(head == null){ return null; } Node dummty = new Node(-1); dummty.next = head; while(head ! = null){ Node temp = new Node(head.val); temp.next = head.next; head.next = temp; head = temp.next; } head = dummty.next; while(head ! = null){ if(head.random ! = null){ head.next.random = head.random.next; } head = head.next.next; } head = dummty.next; Node res = head.next; while(head ! = null){ Node t = head.next; if(head.next ! = null){ head.next = head.next.next; } head = t; } return res; }Copy the code