# Three steps of single linked list problem solving

## 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:

The pointer points to the next node and the endpoint points to null Pointer to the previous node and the next node 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
}
};
```

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) {
while(slow !== fast ) {
if(!fast || !fast.next) return false;
slow = slow.next;
fast = fast.next.next;
}
return true
}
``` ```Example:
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) {
let prev = null;
while(cur) {
const curNext = cur.next;
// Assign to prev pointer after inversion
cur.next = prev;
prev = cur;
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) {
while(fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow
};
```

### 5,Delete the penultimate 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
// 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
};
```

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:
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 = []
}
let pre = 0;
let last = res.length - 1;
while (pre < last) {
if (res[pre] !== res[last]) return false;
pre++;
last--;
}
return true
}
```

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) {
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 carry = 0;
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
}
```Advanced: think about how to solve the problem if these digits are stored forward?