This is the 22nd day of my participation in the August Wen Challenge.More challenges in August

Brush questions, please go to LeetCode to brush questions together when you have time. By brushing questions, you can consolidate the data structure and algorithm foundation. The accumulated improvement is really great, especially now all the better factories will test the algorithm

Today’s content is leetCode reference offer(version 2) 35 and 36, linked list type

It is recommended to brush the same type at a time, for example, do not brush a binary tree and a dynamic planning at a time, brush a type of learning effect is better

Let’s get started

Replication of complex linked lists

The title goes like this:

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

Limitations:

-10000 <= node. val <= 10000 Node.random Indicates null or refers to a Node in the linked list. The number of nodes does not exceed 1000Copy the code

Idea 1: Hash tables

The idea is that you can store any type of key-value feature in a hash table. You first iterate through the list, then copy each node into the hash table, and then iterate through the list again, with the next and random Pointers for each node in the hash table pointing to the corresponding node in the list

// Define a constructor that creates a linked list node
function Node(val, next, random) {
    this.val = val;
    this.next = next;
    this.random = random;
}
function copyRandomList(head){
  if(! head)return null;
  // Create a hash table and take out the header of the list
  let hash = new Map(),node = head
  // Iterate through the linked list, storing each node in the hash table
  while(node) {
    hash.set(node,new Node(node.val));
    node = node.next;
  }
  // Restore the head of the linked list, ready to iterate again
  node = head;
  while(node) {
    // Copy the next pointer and random pointer for each node in the linked list
    hash.get(node).next = node.next ? hash.get(node.next) : null;
    hash.get(node).random = node.random ? hash.get(node.random) : null;
    node = node.next;
  }
  // Returns the header of the new list
  return hash.get(head)
}
Copy the code

The algorithm complexity is

  • Time complexity O(n)
  • Space complexity O(n)

Binary search trees and bidirectional linked lists

The title goes like this:

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 example

We want to turn 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 figure below shows the linked list transformed from the binary search tree above. “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

Idea 1: Middle order traversal + recursion

The idea is, because you need a well-ordered result, you can simply iterate over a middle-order traversal of a binary search tree, because the result of middle-order traversal is an ascending array

Then, if you want to turn it into a two-way circular list, all you need to do is put the right side of the tail node to the first node, and the left side of the first node to the last node

So we create a variable pre that represents the previous node, and then recursively, point the right node of Pre to the current node node, point the left node of the current node node to Pre, and assign Node to Pre

function treeToDoublyList(root) {
    if(! root)return
    // Create a variable that represents the previous node, because pre is null when you recurse to the bottom left node
    // So keep the node as the head of the circular list
    let head = null,pre = head

    dfs(root)

    // After the sequence is completed, pre is the value of the last node, and the previous node in the table header points to pre
    // Add the next node of the Pre to the table header to complete the closed loop
    head.left = pre
    pre.right = head
    return head

    function dfs(root) {
      // The recursive termination condition
      if(! root)return
      // Iterate over the left subtree
      dfs(root.left)
      if(! pre) {// If there is no previous node, the current node is the table header
        head = root
      } else {
        // Otherwise, the right of the previous node is the current node
        pre.right = root
      }
      // Change the direction to establish a two-way relationship
      root.left = pre // Update the pointer to the previous node of the current node
      pre = root // Update the current node, at the end of this iteration, for use in the next iteration
      // Iterate over the right subtree
      dfs(root.right)
    }
}
Copy the code

It’s all in the notes

Today’s brush questions here, if you also want to brush questions, you can encourage each other to exchange

conclusion

Praise and support, hand left lingering fragrance, and have honor yan

Thank you for being here!