This paper introduces the data structure and common operations of linked lists in JavaScript, and introduces the merge deletion, inversion and circular list of linked lists through algorithms.

The data structure

Create a node

// constructor
function ListNode(val) {
    this.val = val;
    this.next = null;
}

const node = new ListNode(1);
node.next = new ListNode(2);
Copy the code

Operation node

  1. insert
// Insert node3 in node1 and node2
const node3 = new ListNode(3);
node3.next = node1.next;
node1.next = node3;
Copy the code
  1. delete

The criteria for deletion are: the existence of a node cannot be traversed during the traversal of the linked list.

// Delete node3 between node1 and node2
node1.next = node1.next.next;
Copy the code

algorithm

The application of linked lists

Key words: front-end node, dummy node

25. Merge two sorted lists

** The essence of dealing with linked lists is to deal with pointer relationships between linked list nodes. ** think of the pointer as a needle, and the node to be sorted as a button. Compare the value of the nodes of the two lists and add the smaller node to the list.

var mergeTwoLists = function(l1, l2) {
    const dummy = new ListNode();
    let cur = dummy;
    while(l1 && l2){
        if(l1.val<=l2.val){
            cur.next = l1;
            l1 = l1.next;
            cur = cur.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
            cur = cur.next;
        }
    }
    cur.next = l1? l1:l2;
    return dummy.next;
};
Copy the code

83. Delete duplicate elements from sorted linked lists

The problem looks at the ability to traverse and delete nodes.

var deleteDuplicates = function(head) {
    let cur = head;
    while(cur! =null&&cur.next! =null) {if(cur.val===cur.next.val){
            cur.next=cur.next.next;
        } else{ cur=cur.next; }}return head;
};
Copy the code

Delete duplicate element II from sorted list

Delete all the nodes that duplicate each other.

So we have to know the precursor of the node to be deleted. To make it easier to handle the first node of a linked list, we need to introduce the dummy node, which is the artificial logical node of the first node.

var deleteDuplicates = function(head) {
    const dummy = new ListNode();
    dummy.next = head;
    let cur = dummy;
    while(cur.next && cur.next.next){
        if (cur.next.val===cur.next.next.val){
            let val= cur.next.val;
            // Delete multiple duplicate nodes
            while(cur.next && cur.next.val===val){ cur.next = cur.next.next; }}else{ cur = cur.next; }}return dummy.next;
};
Copy the code

Fast and slow Pointers and multiple Pointers

A fast or slow pointer means that two Pointers traverse in the same direction, one fast and the other slow.

Key words: fast and slow pointer, multi-pointer, dummy node

Delete the NTH node from the list

Because of the data structure of the linked list, we cannot determine the location of nodes in the list by subscript. If we want to find the NTH node, we have to go through the list twice.

We can use a fast or slow pointer to make the fast pointer n nodes faster than the full pointer, and when the fast pointer reaches the end of the list, the slow pointer points to the precursor of the desired node.

Here we need to use dummy nodes to handle some boundary cases. We need to get into the habit of using dummy nodes.

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode();
    let fast = dummy, slow = dummy;
    dummy.next = head;
    while(n--){
        fast=fast.next;
    }
    while(fast.next){
        fast=fast.next;
        slow=slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
};
Copy the code

206. Reverse linked list – Force link

This problem uses multiple Pointers, three Pointers pre, cur, next to walk through the list. To reverse, point the successor of cur to pre and iterate over it. Next is used to record the original successors of cur.

var reverseList = function(head) {
    let pre = null;
    let cur = head;
    while(cur){
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};
Copy the code

It can also be done recursively:

var reverseList = function(head) {
    if(! head || ! head.next)return head;
    // Reverse the first node of the list
    const node = reverseList(head.next);
    // reverse the successor of the passed node and empty its own successor
    head.next.next = head;
    head.next = null;
    return node;
};
Copy the code

92. Reverse linked list II

Reverse the local list, the idea is to find the start node to reverse, and then reverse. In addition, we have to deal with the first and last nodes of the local list after inversion.

var reverseBetween = function(head, left, right) {
    let dummy= new ListNode();
    dummy.next = head;
    // the p node is used to record position information, which is used to connect the first node after the inversion
    let p = dummy;
    // Find the precursor of the start node to be reversed
    for(let i = 0; i < left - 1; i++){
        p=p.next;
    }
    // Invert, starting from the next node of the start node
    let pre = p.next, cur = pre.next;
    for(let i = 0; i < right - left; i++){
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    // handle the inverted first and last nodes
    p.next.next = cur;
    p.next = pre;
    return dummy.next;
};
Copy the code

Circular linked list

Key words: flag, fast and slow pointer

141. Circular linked lists

The solution is to flag the nodes that have been traversed. If the nodes traversed have been marked, then there is a ring:

var hasCycle = function(head) {
    while(head){
        if(head.flag===true) {return true;
        } else {
            head.flag=true; head=head.next; }}return false;
};
Copy the code

142. Circular linked List II

The first flag node to be found must be the starting point of the ring. The difference is we’re returning nodes of the linked list.

var detectCycle = function(head) {
    while(head){
        if(head.flag===true) {return head;
        } else {
            head.flag=true; head=head.next; }}return null;
};
Copy the code

This problem can also be done using a fast or slow hand, where the slow hand takes one step and the fast hand takes two steps. Let the distance of the fast pointer be 2t, the distance of the slow pointer be t, and the length of the ring be s. Since 2t – t = s, that is, t = s, when the fast and slow Pointers meet, the distance of the slow Pointers is the length of the ring. At this point, the distance between the slow pointer and the start of the ring is the same as the distance between the start of the fast pointer and the start of the ring.

var detectCycle = function(head) {
    const dummy = new ListNode(0);
    dummy.next=head;
    let fast=dummy;
    let slow=dummy;
    while(fast! = =null&&fast.next! = =null){
        fast=fast.next.next;
        slow=slow.next;
        if(slow===fast){
            let newSlow=dummy;
            while(newSlow! ==slow){ newSlow=newSlow.next; slow=slow.next; }returnslow; }}return null;
};
Copy the code

Think twice, code once.