Linked List Theoretical Basics

explain: theoretical basis
Main points:
1. Linked list type: single linked list, double linked list, circular linked list
2. Linked list storage: the memory space is not continuous
3. Linked list definition: the js version is as follows

class ListNode {
  val;
  next = null;
  constructor(value) {
    this.val = value;
    this.next = null;
  }
}

4. Linked list operations: insert, delete, query

203. Remove linked list elements

Topic link: 203. Remove linked list elements

Ideas:
1. Virtual head node: because the head node may be deleted, it needs to be set
2. If the value of next is equal, jump out of this cycle after deletion: because it is necessary to check whether the new next object is also equal to val
3. If not equal, then cur moves to the next node to continue checking cur.next

code:

var removeElements = function(head, val) {
    const ret=new ListNode(0,head);//Virtual head node, you can easily delete the head node
    let cur=ret;//Note that cur here is a linked list node
    while(cur.next){//The access pointer method here is different from CPP, cpp is ->, and here is accessed as an object
        if(cur.next.val===val){
            cur.next=cur.next.next;
            continue;//Need to check whether the updated value of cur.next is still equal to val
        }
        cur=cur.next;//cur update is equal to the next node
    }
    return ret.next;//return head node
};

question:
1. What does the prototype in MyLinkedList.prototype.getNode in the code mean?
2. Does get return val or node?
Answer: I wrote two functions, one returns node and the other returns val. The function that returns node is convenient for other function calls later.
Complexity analysis:
Time complexity: O(n)

707. Design Linked List

Topic link: 707. Design Linked List
Ideas:
1. Need linknode class and mylinknode function to initialize a linked list
2. For the implementation of various methods, see notes for details. Note that a getnode function is defined for later calling.

• get(index): Get the value of the index node in the linked list. Returns -1 if the index is invalid. Here getnode is called, and the virtual head node is used in getnode.
• addAtHead(val): Add a node with value val before the first element of the linked list. After insertion, the new node will be the first node of the linked list. Note that the processing of the tail node when adding a node to an empty list should also be equal to node.
• addAtTail(val): Append the node with value val to the last element of the linked list. Also pay attention to the processing of the head node when adding nodes to the empty linked list.
• addAtIndex(index,val): Add a node with the value val before the index node in the linked list. If index is equal to the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length of the linked list, the node will not be inserted. If index is less than 0, insert the node at the head. Classify and discuss according to the topic, and then call getnode to get the node of index-1.
• deleteAtIndex(index): If the index index is valid, delete the index-th node in the linked list. 1. First discuss the situation where the head node is deleted, that is, if(index === 0). In this case, if the tail node is deleted at the same time (it becomes an empty list after deletion), then the tail node must be equal to the head node The node is null. 2. What is deleted is not the head node, call getnode to get the element of index-1, and then change the value of next. Also pay attention to the case of deleting the tail node, the tail node needs to become the node of index-1.

code:

class LinkNode {
    constructor(val, next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Initialize your data structure here.
 * Singly linked list stores the head and tail nodes and the number of nodes
 */
var MyLinkedList = function() {
    this._size = 0;
    this._tail = null;
    this._head = null;
};

/**
 * Get the value of the index-th node in the linked list. If the index is invalid, return -1. 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.getNode = function(index) {
    if(index < 0 || index >= this._size) return null;
    // Create a virtual head node
    let cur = new LinkNode(0, this._head);
    // 0 -> head
    while(index-- >= 0) {
        cur = cur.next;
    }
    return cur;
};
MyLinkedList.prototype.get = function(index) {
    if(index < 0 || index >= this._size) return -1;
    // Get the current node
    return this.getNode(index).val;
};

/**
 * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    const node = new LinkNode(val, this._head);
    this._head = node;
    this._size++;
    if(!this._tail) {
        this._tail = node;
    }
};

/**
 * Append a node of value val to the last element of the linked list. 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    const node = new LinkNode(val, null);
    this._size++;
    if(this._tail) {
        this._tail.next = node;
        this._tail = node;
        return;
    }
    this._tail = node;
    this._head = node;
};

/**
 * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    if(index > this._size) return;
    if(index <= 0) {
        this.addAtHead(val);
        return;
    }
    if(index === this._size) {
        this.addAtTail(val);
        return;
    }
    // Get the previous node of the target node
    const node = this.getNode(index - 1);
    node.next = new LinkNode(val, node.next);
    this._size++;
};

/**
 * Delete the index-th node in the linked list, if the index is valid. 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    if(index < 0 || index >= this._size) return;
    if(index === 0) {
        this._head = this._head.next;
        // If the deleted node is also a tail node, the tail node should be processed
        if(index === this._size - 1){
            this._tail = this._head
        }
        this._size--;
        return;
    }
    // Get the previous node of the target node
    const node = this.getNode(index - 1);    
    node.next = node.next.next;
    // Handle tail nodes
    if(index === this._size - 1) {
        this._tail = node;
    }
    this._size--;
};

question:
The idea is good, but in fact, the code I wrote has been debug ged for a long time, and I am not familiar with the js syntax. I don’t know the definition of js pointers and the writing of js classes and objects.

206. Reverse Linked List

Topic link: 206. Reverse Linked List

Ideas:
1. Double pointers actually need three pointers, pre, cur and temp respectively record three nodes.
2. Recursion. Two parameters, recursively update pre and head each time, and use temp to record before head.next changes.

code:

// Double pointer:
var reverseList = function(head) {
    if(!head || !head.next) return head;
    let temp = null, pre = null, cur = head;
    while(cur) {
        temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    // temp = cur = null;
    return pre;
};

// recursion:
var reverse = function(pre, head) {
    if(!head) return pre;
    const temp = head.next;
    head.next = pre;
    pre = head
    return reverse(pre, temp);
}

var reverseList = function(head) {
    return reverse(null, head);
};

Complexity analysis:
Time complexity: O(n)

Summary of impressions

1. I still read a lot of problem solutions today. I was familiar with the js syntax when I brushed it for the third time. If you are familiar with the ideas, you should be able to tear it up by hand.
2. I am not familiar with js functions and pointers. I plan to read them all today to solve the problems in the brush questions.
3. Designing the debug of the linked list has not been done for a long time. Tomorrow, I must learn how to print logs and how to run and debug locally.