Introduction of the list

What is a linked list?

  • A list of multiple elements.
  • The elements are stored discontiguously, connected by the next pointer

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, no need to move elements, just change the point to next.

Linked list in JS

  • There are no linked lists in JavaScript
  • You can use Object to simulate linked lists

Code demo

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;

// Iterate over the list
let p = a;
while(p){
    console.log(p.val);
    p = p.val;
}
/ / insert
const e = {val:'e'};
c.next = e;
e.next = d;
/ / delete
c.next = d;
Copy the code

LeetCode:237. Delete a node from a linked list

Their thinking

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

The problem solving steps

  • Change the value of the truncated point to the value of the next node.
  • Delete the next node.

Code solution:

/** * 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

LeetCode206: Reverse linked lists

Their thinking

  • Reverse the two nodes: point next of n+1 to n
  • Reverse multiple nodes: Double pointer traverses the list, repeating the above operation

The problem solving steps

  • Two Pointers traverse the linked list one after the other
  • Reversed double pointer

Answer key coding:

/** * 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){
        let temp = p1.next;
        p1.next = p2;
        p2 = p1;
        p1 = temp;
    }
    return p2; 
};
Copy the code

LeetCode2: add two numbers

Their thinking

  • Elementary school math problem, simulation addition operation
  • You need to walk through the list

The problem solving steps

  • 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 and reserving the tens digit for the next digit to add

Answer key coding:

/** * 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) {
    let l3 = new ListNode(0);
    let p1 = l1, p2 = l2, 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);
        
        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

LeetCode83: Removes duplicate elements from sorted linked lists

Their thinking

  • Because lists are ordered, repeating elements must be 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

The problem solving steps

  • Iterate through the list and delete the next element if the current element is found to have the same value as the next element
  • After traversal, return to the head of the original list

Answer key Coding:

/** * 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

Leetcode141: Circular linked list

Their thinking

  • Two people start at the same time from the starting point of the circular playground, and the fast one is sure to pass the slow one lap
  • Use a fast pointer and a slow pointer to traverse the linked list. If the Pointers can meet, the linked list has a circle

The problem solving steps

  • Traverse the list with a fast pointer and a slow pointer, returning true if the Pointers can meet
  • After traversal, return false if no encounter has occurred

Answer key coding:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function(head) {
    let p1 = head ,p2 = head;
    while(p1 && p2 && p2.next){
        p1 = p1.next;
        p2 = p2.next.next;
        if(p1 === p2){
            return true; }}return false;
};
Copy the code