1. LinkedList profiles

1.1 What is a linked list?

  • A list of multiple elements
  • Element storage is not contiguous and is linked together by the next pointer

1.2 Arrays VS linked lists

  • Arrays: Adding and removing non-beginning and end elements often requires moving elements
  • Linked list: add and remove non-beginning and end elements, do not move elements, only need to changenextCan point to.

Linked lists in 1.3 JS

  • There are no linked lists in JavaScript
  • You can use the ObjectsimulationThe list

1.4 Code

Create, traverse, insert, delete

const a = { val: 'a' };
const b = { val: 'b' };
const c = { val: 'c' };
const d = { val: 'd' };
a.next = b;
b.next = c;
c.next = d;

/ * * generated following structure {" val ":" a ", "next" : {" val ":" b ", "next" : {" val ":" c ", "next" : {" val ":" d "}}}} * /


// Iterate over the list
let p = a;
while (p) {
    console.log(p.val);
    p = p.next;
}

// Insert the list into e
const e = { val: 'e' };
c.next = e;
e.next = d;

// delete e from the list
c.next = d;

Copy the code

2. LeeCode: 237. Delete nodes in the linked list

delete-node-in-a-linked-list

Leetcode-cn.com/problems/de…

2.1 Solution ideas

  • The last node of the deleted node cannot be obtained directly
  • Move the deleted node to the next node

2.2 Steps to solve the problem

  • Change the value of the deleted node to the value of the next node
  • Delete the next node
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};
Copy the code

3. LeeCode: 206. Reverse linked lists

reverse-linked-list

Leetcode-cn.com/problems/re…

3.1 Solution idea

  • Reverse the two nodes: point next of n+1 to n
Input:... -> n -> n+1 ->... Output:... -> n+1 -> n ->...Copy the code
  • Reverse multiple nodes: Double pointer traverses the list, repeating the above operation
Input: 1 - > 2 - > 3 - > 4 - > 5 - > NULL output: 5 - > 4 - > 3 - > 1 - > 2 - > NULLCopy the code

3.2 Steps to solve the problem

  • Two Pointers traverse the linked list one after the other
  • Reversed double pointer
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let p1 = head;
    let p2 = null;
    while(p1){
        const tmp = p1.next;
        p1.next = p2;
        p2 = p1;
        p1 = tmp;
    }
    return p2
};
Copy the code

4. LeeCode: 2. Add two numbers

add-two-numbers

Leetcode-cn.com/problems/ad…

4.2 Solution Idea

  • Math problem, simulated addition operation
  • You need to walk through the list
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Cause: 345 + 465 = 807Copy the code

4.3 Steps to solve the problem

  • Create an empty linked list
  • Iterate over the two lists to be added, simulating the addition operation, appending the units digit to the new list, leaving the tens digit to be added
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var addTwoNumbers = function(l1, l2) {
    const l3 = new ListNode(0)
    let p1 = l1;
    let p2 = l2;
    let p3 = l3;

    let carry = 0; 
    while(p1 || p2) {
        const v1 = p1 ? p1.val : 0;
        const v2 = p2 ? p2.val : 0;
        const val = v1 + v2 + carry;
        carry = Math.floor(val / 10)
        p3.next = new ListNode(val % 10)
        // Move the pointer back one bit
        if(p1) p1 = p1.next;
        if(p2) p2 = p2.next;
        p3 = p3.next;
    }
    if(carry){
        p3.next = new ListNode(carry)
    }
    return l3.next;
};
Copy the code

5. LeeCode: 83. Delete duplicate elements from sorted lists

remove-duplicates-from-sorted-list

Leetcode-cn.com/problems/re…

5.1 Solution Ideas

  • Because lists are ordered, repeating elements are adjacent
  • Iterate through the list and delete the next element if the current element is found to have the same value as the next element.
Input: 1 -> 1 -> 2 Output: 1 -> 2Copy the code

5.2 Steps to solve the problem

  • Iterate through the list and delete the next element if the current element is found to have the same value as the next element
  • At the end of the traversal, return the head of the original list
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var deleteDuplicates = function(head) {
    let p = head;
    while (p && p.next) {
        if(p.val === p.next.val){
            p.next = p.next.next;
        }else{ p = p.next; }}return head
};
Copy the code

6. LeetCode: 141

7. Front ends and linked lists: Prototype chains in JS

8. Front-end and linked list: Use the linked list pointer to get JSON node values

9. Linked list – Summary

9.1 Technical Points

  • The elements in the list are not stored contiguously and are connected by next
  • There are no linked lists in JavaScript, but you can simulate them with Object
  • Linked list common operations: modify linked list, traversal linked list
  • The prototype chain in JS is also a linked list
  • Use the linked list pointer to get the value of the JSON node