“🌟🌟🌟🌟🌟“

“Taste: Garlic and Dutch beans“

“Cooking time: 8min“

Github github.com/Geekhyt, welcome to the canteen, if you think the food is delicious, a Star is a great encouragement to the canteen owner.

The series of columns on data structures and algorithms follows, if you haven’t tried it yet.

  • How the front end handles data structures and Algorithms (Pilot)
  • Time and space complexity analysis of JavaScript algorithm
  • Do you really understand recursion?
  • Divide and conquer, dynamic programming, backtracking, greed
  • The tree industry has a specialty
  • Binary search algorithms from drinking table games

The list

Arrays are familiar, and we manipulate them almost every day. So let’s compare arrays to learn linked lists. First of all, it should be clear that the underlying storage structure of linked lists and arrays is different. Arrays require storage in a contiguous piece of memory, while linked lists are connected by Pointers to a group of discrete memory blocks. Visible lists require less memory, but random access performance is not as good as arrays, requiring O(n) time complexity.

The following figure shows singly linked lists and the addition and deletion of singly linked lists. In fact, the essence of a singly linked list operation is to handle Pointers between linked list nodes.


In the operation of deleting a linked list node, we only need to move the next pointer of the precursor node that needs to be deleted to the next node. Thus, the currently deleted node is discarded in memory, waiting to be cleared by the garbage collector.

To make it easier for you to understand, a linked list can be compared to a train in real life, where each carriage of a train is a node in a linked list. Carriages are connected to each other and can be added or removed. During the Spring Festival travel rush, the passenger volume is relatively large, and the train will generally add carriages.

The node structure of a linked list is composed of data fields and pointer fields. In JavaScript, it is implemented in the form of nested objects.

{
    / / data domain
    val: 1.    / / pointer field
    next: {
 val:2. next:... } } Copy the code

Popular science noun

  • Header: The header is used to record the base address of the linked list and is the starting point for traversing the list
  • Tail node: The pointer to the tail node does not point to the next node, but to an empty address, NULL
  • Singly linked lists: Singly linked lists are one-way, with only a successor pointer next to the next node and a tail pointer to an empty address
  • Circular lists: A pointer to the tail of a circular list points to the head of the list
  • Two-way chain table: two-way chain table support in both directions, each node has more than one next to the following at the back of the node, a node of prev precursor pointer pointing to the front, two-way chain table takes up more memory, but to find precursors node time complexity is O (1), insert, and delete operations than singly linked lists are more efficient
  • Bidirectional circular linked lists

Circular linked list


Two-way linked list


Bidirectional circular linked lists


LeetCode bo

After mastering the basic knowledge of linked list, let’s practice with some LeetCode exercises of linked list. Click the title of the topic to jump to the description page of the related topic.

1. Merge two ordered lists

Train of thought

  • Use recursion to solve the problem
  • Merge the smaller of the two list heads with the remaining elements
  • The recursion terminates when one of the two lists is empty

Complexity analysis

N plus M is the length of the two lists

  • Time complexity: O(M+N)
  • Space complexity: O(M+N)
const mergeTwoLists = function (l1, l2) {
    if (l1 === null) {
        return l2;
    }
    if (l2 === null) {
 return l1;  }  if (l1.val < l2.val) {  l1.next = mergeTwoLists(l1.next, l2);  return l1;  } else {  l2.next = mergeTwoLists(l1, l2.next);  return l2;  } }; Copy the code

2. Circular lists

Train of thought

  • Double pointer method
  • The fast pointer moves two steps at a time and the slow pointer moves one step at a time
  • If there is no loop, the fast pointer reaches the tail first, returning false
  • If there are rings, they must meet

Complexity analysis

  • Time complexity: O(N)
  • Space complexity: O(1)
const hasCycle = function(head) {
    if(! head || ! head.next) {        return false;
    }
    let fast = head.next;
 let slow = head;  while(fast ! == slow) { if(! fast || ! fast.next) { return false;  }  fast = fast.next.next;  slow = slow.next;  }  return true; }; Copy the code

Train of thought

  • notation
  • The linked list is traversed to determine whether there is a ring by the tag, and if the tag exists, there is a ring.

Complexity analysis

  • Time complexity: O(N)
  • Space complexity: O(1)
const hasCycle = function(head) {
    while (head) {
        if (head.flag) {
            return true;
        } else {
 head.flag = true;  head = head.next;  }  }  return false; } Copy the code

3. Reverse the list

Train of thought

  • The iteration
  • Initialize the precursor node to NULL and the target node to the head node
  • Iterate through the list, recording the next node and reversing the pointer
  • The prev and CURr Pointers move forward one step each
  • After the inversion, the prev becomes the head node of the new list

Complexity analysis

  • Time complexity: O(N)
  • Space complexity: O(1)
const reverseList = function(head) {
    let prev = null;
    let curr = head;
    while(curr ! = =null) {
        let next = curr.next;
 curr.next = prev;  prev = curr;  curr = next;  }  return prev; }; Copy the code

4. Delete the NTH node from the penultimate node

Train of thought

  • Delete the NTH node, we need to find the NTH +1 node, delete the next node
  • Add prev nodes, also called sentinel nodes, to handle boundary problems
  • With the two-pointer method, the fast pointer moves n+1 first, then the fast and slow Pointers move forward synchronously until fast. Next is null
  • Delete the NTH to last node and return prev.next

Complexity analysis

  • Time complexity: O(N)
  • Space complexity: O(1)
const removeNthFromEnd = function(head, n) {
    let prev = new ListNode(0);
    prev.next = head;
    let fast = prev;
    let slow = prev;
 while (n--) {  fast = fast.next;  }  while (fast && fast.next) {  fast = fast.next;  slow = slow.next;  }  slow.next = slow.next.next;  return prev.next; }; Copy the code

5. Find the intermediate node of the linked list

Train of thought

  • Double pointer method
  • The fast pointer moves two steps at a time and the slow pointer moves one step at a time
  • When the fast hand reaches the end, the slow hand just goes to the middle

Complexity analysis

  • Time complexity: O(N) N is the number of nodes in a given linked list
  • Space complexity: O(1) only needs constant space to store two Pointers slow and fast
const middleNode = function(head) {
    let fast = head;
    let slow = head;
    while (fast && fast.next) {
        slow = slow.next;
 fast = fast.next.next;  }  return slow; }; Copy the code

❤️ Love triple punch

1. Please give me a “like” when you see this. Your “like” is the motivation for my creation.

2. Pay attention to the front canteen of the public account, “your front canteen, remember to eat on time”!

3. This article has been included in the front canteen Github github.com/Geekhyt, for a small Star, thanks to Star.