This is the 29th day of my participation in the August More Text Challenge

Replication of complex linked lists

Copy of complex linked lists

Difficulty: Medium

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

Answer key

Difficulty: In this case, the random pointer is added, and the random reference pointing of each node of the new linked list is required in the process of copying the linked list, as follows: (The pointing of random cannot be determined)

var copyRandomList = function(head) {
  let cur = head;
  let dum = new Node(0), pre = dum;
  while(! cur){let node = new Node(cur.val); // Copy the node cur
    prev.next = node;							// The first node of the new list -> the current node
    // prev.random = ??? // Can not be determined
    cur = cur.next;								// Iterate over the next node
    pre = node;										// Save the current node
  }
  return dum.next;
};
Copy the code

Method one hash table

By using the query characteristics of hash table, the key-value pair mapping relationship between the original linked list node and the corresponding node of the new linked list is constructed, and then the next and random reference points of each node of the new linked list are iterated.

Process:

  1. If head is empty, null is returned.
  2. Initialize: Create a new hash table with the node cur pointing to the head node.
  3. Copy the list:
    1. Create new nodes and add key-value pairs (old cur nodes, new cur nodes) to the map.
    2. Cur traverses to the next node in the original list.
  4. Build a reference point to the new list:
    1. Build new nodes next and random reference points to.
    2. Cur traverses to the next node in the original list.
  5. Return value: the head node of the new list.
/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; *}; * /

/ * * *@param {Node} head
 * @return {Node}* /
var copyRandomList = function(head) {
  if(! head)return null;
  const map = new Map(a);// Create a hash table
  let cur = head;  
  while(cur){
    map.set(cur,new Node(cur.val))
    cur = cur.next;
  }
  cur = head;
  
  while(cur){
   	map.get(cur).next = cur.next ? map.get(cur.next) : null;
    map.get(cur).random = cur.random ? map.get(cur.random) : null;
    cur = cur.next;
  }
  return map.get(head);
};
Copy the code

  • Time complexity O(N) : two rounds of traversal

  • Space complexity O(N) : Extra space to use hash tables

Method two splicing + split

Build old node 1 -> new node 1 -> Old node 2 -> new node 2 ->… In this way, it is convenient to find the random pointing node of the old node while finding the random pointing node of the new node.

Steps:

  1. Copy each node and build a spliced linked list
  2. Construct the random pointing of each new node. When cur.random is visited, the random pointing node corresponding to the new node cur.random is cur.random.next.
  3. Split the old and new lists. Set pre and CUR to point to the head node of the old list and the new list respectively. Separate pre and CUR through traversal.
  4. Returns the head node res of the new list.
var copyRandomList = function(head) {
  if(head === null) return null;
  // 1. Copy each node and build a spliced linked list
  while(cur){
    let tmp = new Node(cur.val);
    tmp.next = cur.next;
    cur.next = tmp;
    cur = tmp.next;
  }
  // 2. Construct a random pointer to each new node
  cur = head;
  while(cur){
    if(cur.random){
      cur.next.random = cur.random.next;
    }
    cur = cur.next.next;
  }
  // 3. Split two linked lists
  cur = head.next;
  let pre = head, res = head.next;
  while(cur.next){
    pre.next = pre.next.next;
    cur.next = cur.next.next;
    pre = pre.next;
    cur = cur.next;
  }
  pre.next = null; // Handle the tail of the old list
  return res;	// Return the new list head node
}
Copy the code
  • Time complexity O(N) : three rounds of traversal
  • Space complexity O(1) : Reference variables use constant size space.

Binary search trees and bidirectional linked lists

36. Binary search tree with bidirectional linked list

Difficulty: Medium

Address: leetcode-cn.com/problems/er…

Enter a binary search tree and convert the binary search tree into a sorted circular bidirectional list. You cannot create any new nodes. You can only adjust the Pointers to nodes in the tree.

To give you a better understanding of the problem, take the following binary search tree as an example:

We want to convert this binary search tree into a bidirectional circular list. Each node in a linked list has a precursor and a successor pointer. For a bidirectional circular list, the first node is preceded by the last node, and the last node is succeeded by the first node.

The above binary search tree is transformed into a linked list shown below. “Head” refers to the node with the smallest element in the list.

In particular, we want to be able to do the conversion in place. When the transformation is complete, the left pointer of the node in the tree needs to point to the precursor, and the right pointer of the node in the tree needs to point to the successor. You also need to return a pointer to the first node in the list.

Answer key

According to the properties of binary search tree, it can be inferred that middle-order traversal should be adopted.

Method 1 recursion in order traversal

/ * * *@param {Node} root
 * @return {Node}* /
var treeToDoublyList = function(root){
  if(! root)return;
  let head = null;
  let pre = head;
  inorder(root);
  head.left = pre;
  pre.right = head;
  return head;
 / * * *@param {Node} node* /
  function inorder(node){
    if(! node)return;
    // Iterate over the left subtree
    inorder(node.left,pre);
    // Iterate over the current root node
    if(! pre){// Traverse to the smallest node (the leftmost node), which is the head of the bidirectional list
      head = node;
    }else{
      pre.right = node;
    }
    node.left = pre;
    pre = node;
    // Iterate over the right subtreeinorder(node.right,pre); }}Copy the code
  • Time complexity O(N)
  • Space complexity O(N)

Method two is non-recursive order traversal

Use stacks to simulate recursive processes

var treeToDoublyList = function(root) {
  if(! root)return;
  const stack = [];
  let node = root
  let pre = null;
  let head = null;
  while(stack.length || node){
    if(node){
      stack.push(node);
      node = node.left;
    }else{
      const top = stack.pop();
      if(! pre){ head = top; }else{
        pre.right = top;
      }
      top.left = pre;
      pre = top;
      node = top.right;// To traverse the right subtree
    }
  }
  head.left = pre;
  pre.right = head;
  return head;
}
Copy the code

Practice every day! The front end is a new one. I hope I can get a thumbs up