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