The list

Dummy nodes and iterative methods in general (list traversal)

In linked lists, the so-called iterative method is mostly used to compare the current node with the next node, so we carry out the iteration of a method.

Iterative method regular scale edition

    function iteration(listNums){
        const dummy = new ListNode(0)
        dummy.next = listNums
        // define TMP to operate on the linked list
        let tmp = dummy
        
        while(End condition){if(Curr compares next to curr){... options// tmp.next = tmp.next.next
            }else{
                tmp = tmp.next
            }
        }
        return dummy
Copy the code

Removes linked list elements

The recursive method

The definition of linked list is recursive, so linked list problems can often be solved recursively. This problem requires the deletion of all nodes in the linked list whose value is equal to a specific value. It can be implemented recursively.

For a given linked list, all nodes except head are deleted, and then the value of head is determined to be equal to the given val. If the value of head is equal to val, then head needs to be deleted, so the head node after deletion is head.next. If the node value of head is not equal to val, head is retained, so the head node after the delete operation is head. The above process is a recursive process.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} val
 * @return {ListNode}* /
var removeElements = function(head, val) {
    if(! head)return head
    head.next = removeElements(head.next,val)
    return head.val == val ? head.next : head
};
Copy the code

Iterative method

Iterate over Next with dumb (dirty) nodes

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} val
 * @return {ListNode}* /
var removeElements = function(head, val) {
    const dummy = new ListNode(0,head)
    let temp = dummy

    while(temp.next){
        if(temp.next.val == val){
            temp.next = temp.next.next
        }else {
            temp = temp.next
        }
    }

    return dummy.next   
};
Copy the code

Merge two ordered lists

The recursive method

var mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2;
    } else if (l2 === null) {
        return l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        returnl2; }};Copy the code

Iterative method

var mergeTwoLists = function(l1, l2) {
    let ans = new ListNode(0)
    let tmp =ans

    while(l1 ! =null&& l2 ! =null) {if(l1.val>=l2.val){
            tmp.next = l2
            l2 = l2.next
        }else{
            tmp.next = l1
            l1 = l1.next
        }
        tmp = tmp.next
    }

    tmp.next =l1 == null ? l2 : l1

    return ans.next
};

Copy the code

Delete duplicate elements from sorted linked lists

var deleteDuplicates = function(head) {
    var cur = head;
    // Determine that both the head and the next node must exist at the same time or it is not necessary
    while(cur && cur.next) {
        if(cur.val == cur.next.val) {
            cur.next = cur.next.next;
        } else{ cur = cur.next; }}return head;
};
Copy the code

02.01. Remove duplicate nodes

 // The dummy node + hash table
var removeDuplicateNodes = function(head) {
    const directory = {}
    const flag = new ListNode(0)
    flag.next = head
    let tmp = flag

    while(tmp.next){
        let val = tmp.next.val
        if(! directory[val]){ directory[val] =true
            tmp = tmp.next
        }else{
            tmp.next = tmp.next.next
        }
    }

    return flag.next
};
Copy the code

Double pointer/fast and slow pointer method

206. Reverse linked lists

    var reverseList = function(head){
        let prev = null
        let cur = head
        while(cur){
            let next = cur.next
            next = prev
            prev = cur
            cur = next
        }
        return prev
    }

Copy the code

22. The k last node in the linked list

  var reverseList = function(head) {
      let curr = head
      let prev = null

      while(curr){
          let next = curr.next
          curr.next = prev
          prev = curr
          curr = next
      }
      return prev
};
Copy the code

The middle node of a linked list

An array of ideas

The disadvantage of linked lists is that they cannot have index values like array structures, so we can solve some problems by introducing the idea of arrays. Here is a reference to the idea of arrays.

var middleNode = function(head) {
    const ans = []

    while(head){
        ans.push(head.val)
        head = head.next
    }
    let mid = parseInt(ans.length / 2)
    console.log(ans[mid])

    return ans[mid]
};
Copy the code

How fast a pointer

Using fast and slow Pointers can solve many problems, as long as the fast pointer 2 steps at a time, slow pointer 2 steps at a time.

var middleNode = function(head) {
    let slow = head
    let fast = head

    while(fast && fast.next){
        slow = slow.next
        fast = fast.next.next
    }

    return slow
};
Copy the code