1, Concept

The linked list is composed of a group of scattered nodes connected by pointers. Each node contains the current node content and subsequent pointers. Compared with array, it is not restricted by storage space and can be inserted and deleted more quickly. There are mainly the following types:

1. Single linked list

The pointer points to the next node and the endpoint points to null

2. Double linked list

Pointer to the previous node and the next node

3. Circular linked list

The last node points to the first node

When solving problems related to linked lists, it will be clearer to perform three steps first and then tap the code

• Determine the type of linked list for problem solving
• Draw pictures and clarify ideas
• Determining boundary conditions

Unlike arrays, JS has not yet provided a direct linked list API. Linked lists can be simulated through objects. The structure is

const head = {
  data: 1,
  next: {
    data: 2,
    next: null,
  },
};

2, leetcode most common related questions

1,Merge two ordered linked lists

Merge the two ascending linked lists into a new ascending linked list and return. The new linked list is composed by splicing all nodes of the given two linked lists

Example:
  input: l1 = [1,2,4], l2 = [1,3,4]
  output: [1,1,2,3,4,4]

Steps:

• The linked list type for problem solving is single linked list
• Idea:
  • L1 and L2 are sequentially increasing, so l1 Val and l2 The smaller value of Val is the minimum value of the merged linked list
  • Recurse the comparison of size nodes in turn until L1 and L2 are null
• Boundary condition: recursion can be stopped when any linked list is null, and the next point to another linked list

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(l2.next, l1)
        return l2
    }
};

2,Circular linked list

Given a linked list, judge whether there are links in the linked list. If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. If there are rings in the linked list, return true; otherwise, return false. O(1) memory is required to solve this problem

pos indicates that the end of the linked list is connected to the position in the linked list. If pos is -1, there is no ring in the linked list

Example:
  Input: head = [3,2,0,-4], pos = 1 
  Output: true  // There is a ring in the linked list, and its tail is connected to the second node

Steps:

• The linked list type for problem solving is single linked list
• Idea:
  • Tortoise and rabbit race algorithm: use the fast and slow double pointers, the fast pointer takes two steps, and the slow pointer takes one step
  • If there are links in the linked list, two pointers with different speeds must meet. And go down from the meeting point and the chain header node at the same time, and you will meet at the starting point of the ring
• Boundary conditions:
  • Fast pointer to null stop, no loop
  • The fast and slow pointers point to the same node with a ring

var hasCycle = function(head) {
    if(!head || !head.next) return false;
    let slow = head.next;
    let fast = head.next.next;
    while(slow !== fast ) {
        if(!fast || !fast.next) return false;
        slow = slow.next;
        fast = fast.next.next;
    }
    return true
}

3,Reverse linked list

Here is the head node of the single linked list. Please use iteration or recursion to reverse the linked list and return the reversed linked list

Example:
  input: head = [1,2,3,4,5]
  output: [5,4,3,2,1]

Steps:

• The linked list type for problem solving is single linked list
• Iteration idea:
  • Point the subsequent pointer of each node of the single linked list to its predecessor node

• Boundary conditions:
  • Stop when the linked list is null
  • The linked list has only one node

var reverseList = function(head) {
    if(!head || !head.next) return head;
    let prev = null;
    let cur = head;
    while(cur) {
        const curNext = cur.next;
        // Assign to prev pointer after inversion
        cur.next = prev;
        prev = cur;
        // Link to next node
        cur = curNext;
    }
    return prev
};

4,Intermediate node of linked list

Given a non empty single linked list whose head node is head, return the intermediate node of the linked list. If there are two intermediate nodes, return the second intermediate node (the number of nodes in the given linked list is between 1 and 100)

Example:
  input: [1,2,3,4,5]
  output:  3
  input: [1,2,3,4,5,6]
  output:  4

Steps:

• The linked list type for problem solving is single linked list
• Idea:
  • The displacement of the fast pointer p2 is twice that of the slow pointer p1, so when p2 reaches the end of the list, p1 has just walked half way and points to the midpoint of the list.
  • The same is true for the following questions

• Boundary conditions:
  • When the fast pointer points to null, the slow pointer is just in the middle position

var middleNode = function(head) {
    if(!head || !head.next) return head;
    let slow = head;
    let fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow
};

5,Delete the penultimate node of the linked list

Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list

Example:
  Input: head = [1,2,3,4,5], n = 2
  Output:[1,2,3,5]

Steps:

• The linked list type for problem solving is single linked list

• Idea:

  • The fast pointer walks through n nodes at a time, and then the two pointers walk back together until the fast pointer points to null. At this time, the slow pointer is the penultimate node
  • Add sentry to process the nth node

• Boundary conditions:

  • When the fast pointer points to null, the position of the slow pointer is the penultimate node

const removeNthFromEnd = function (head, n) {
  // sentry
  let preHead = new ListNode(0)
  preHead.next = head
  let slow = preHead;
  let fast = preHead;
  // Take n steps first
  while (n--) {
    fast = fast.next
  }
  // went together
  while (fast && fast.next) {
    fast = fast.next
    slow = slow.next
  }
  slow.next = slow.next.next
  return preHead.next;
};

6,Palindrome linked list

Give you a head node of the single linked list. Please judge whether the linked list is a palindrome linked list. If yes, return true; Otherwise, false is returned

Example:
  input: head = [1,2,2,1]
  output: true

Steps:

• The linked list type for problem solving is single linked list

• Idea:

  • Throw the linked list into the array with the help of the array
  • Set the front and rear pointers. The front and rear pointers should be the same. If they are different, they are not palindromes
  • If the loop ends without returning false, it is a palindrome

• Boundary conditions:

  • Inconsistent front and rear pointers
  • End of cycle

var isPalindrome = function (head) {
  const res = []
  while (head) {
    res.push(head.val);
    head = head.next
  }
  let pre = 0;
  let last = res.length - 1;
  while (pre < last) {
    if (res[pre] !== res[last]) return false;
    pre++;
    last--;
  }
  return true
}

8,Intersecting linked list

Here are the head nodes headA and headB of the two single linked lists. Please find and return the starting node where the two single linked lists intersect. The topic data ensures that there are no rings in the whole chain structure.

be careful:

• After the function returns the result, the linked list must maintain its original structure (the new linked list needs to be copied)
• If two linked lists have no intersection, null is returned
• The program shall be full of O(n) time complexity and only use O(1) memory

Example:
    Input: intersectVal = 4, listA = [1,2,3,4,5], listB = [6,7,4,5], skipA = 3, skipB = 2   // In A, there are 3 nodes before the intersection node; In B, there are 2 nodes before the intersection node
    Output: Intersected at '4'  // The value of the intersection node is 4 (note that if two linked lists intersect, it cannot be 0)

Steps:

• The linked list type for problem solving is single linked list
• Idea:
  • As above, find the height difference of AB linked list and eliminate it. The length after the known intersection point must be equal
  • AB double pointers advance at the same time. When the pointer traversal of the short linked list B is completed, the length difference of the double pointers is just the length difference of the double linked list. Point the B pointer to the head node of the A linked list, and follow the A pointer to traverse again until the pointer traversal of A is completed
  • Similarly, if the A pointer points to the head node of the B linked list, and the B pointer moves forward, the height difference of the linked list is eliminated

• Boundary conditions:
  • Switch to point to linked list when pointer points to null
  • AB linked list values are equal

var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) return null;
  let pA = headA;
  let pB = headB;
  while (pA !== pB) {
    pA = pA !== null ? pA.next : headB;
    pB = pB !== null ? pB.next : headA;
  }
  return pA;
}

9,List summation

Given two integers represented by a linked list, each node contains a digit. These digits are stored in reverse, that is, a digit is arranged at the head of the linked list. Write a function to sum the two integers and return the result in the form of a linked list

Example:
  Input:(7 -> 1 -> 6) + (5 -> 9 -> 2)，617 + 295
  Output: 2 -> 1 -> 9，I.e. 912

Steps:

• The linked list type for problem solving is single linked list

• Idea:

  • The output is a new linked list, so you need to create a linked list
  • Because of the reverse storage, the linked list is calculated from the single digit, and if it is greater than ten, it is carried
  • For carry, first consider "carry" to store each carry, and the remainder is stored in the created node

• Boundary conditions:

  • When the double linked list points to null, the traversal is completed
  • The traversal is completed. If the carry is not 0, it needs to advance one bit

const addTwoNumbers = function (l1, l2) {
  // sentry
  let preHead = new ListNode(0)
  let carry = 0;
  let pre = preHead;
  while (l1 || l2) {
    let sum = 0;
    if (l1) {
      sum += l1.val
      l1 = l1.next
    }
    if (l2) {
      sum += l2.val
      l2 = l2.next
    }
    sum += carry
    carry = Math.floor(sum / 10)
    pre.next = new ListNode(sum % 10)
    pre = pre.next
  }
  if (carry > 0) {
    pre.next = new ListNode(carry)
    pre = pre.next
  }
  return preHead.next
}

Advanced: think about how to solve the problem if these digits are stored forward?
  Input:(6 -> 1 -> 7) + (2 -> 9 -> 5)，617 + 295
  Output: 9 -> 1 -> 2，I.e. 912