# 3. Delete a node

## 2021.03.04

### Remove a linked list element

Removes all nodes in the list equal to the given value **_val _**. Example: input: 1 – > 2 – > 6 – > 3 – > 4 – > 5 – > 6, val = 6 output: 1 – > 2 – > 3 – > 4 – > 5

#### Solution:

``````/* * @lc app=leetcode.cn id=203 lang=javascript * * [203] Remove list elements */

// @lc code=start
/** * 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) {

let p = phead = new ListNode(null);
while(p.next) {
if(p.next.val == val) {
p.next = p.next.next;
} else{ p = p.next; }}return phead.next;
};
Copy the code``````

The construction of a linked list, using dummy nodes to construct a header pointer for double pointer traversal

## 2021.03.06

### Delete the NTH reciprocal node of the linked list

Give you a linked list, remove the NTH node from the reciprocal of the list, and return the head node of the list.

Advanced: Can you try using a scan implementation?

Example 1:

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

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

Input: head = [1,2], n = 1

Tip:

The number of nodes in the list is sz 1 <= sz <= 30 0 <= node. val <= 100 1 <= n <= sz

#### Solution a:

``````/* * @lc app=leetcode.cn id=19 lang=javascript * * [19] Delete the NTH node */

// @lc code=start
/** * 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} n
* @return {ListNode}* /
var removeNthFromEnd = function(head, n) {
// Change the q pointer to q = head.next··· Next has n next
for( let _n = n; _n > 0; _n-- ) {
};

// Stop traversal when q is null
while(q) {
p = p.next;
q = q.next;
m = m.next;
};

// Delete the node of q
p = p.next;
m.next = p;

};
Copy the code``````

#### Scheme 2:

``````/* * @lc app=leetcode.cn id=19 lang=javascript * * [19] Delete the NTH node */

// @lc code=start
/** * 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} n
* @return {ListNode}* /
var removeNthFromEnd = function(head, n) {
let lastN = 0;

const recursion = (head) = > {
}

lastN++;

if (lastN === n) {
}

if (lastN === n + 1) {
}

};

};
Copy the code``````

#### Solution 3:

``````/* * @lc app=leetcode.cn id=19 lang=javascript * * [19] Delete the NTH node */

// @lc code=start
/** * 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} n
* @return {ListNode}* /
var removeNthFromEnd = function(head, n) {

}

let lastN = 0;

lastN++;

if (lastN - 1 === n) {
}

};
Copy the code``````

There are three schemes: 1. Set the distance between fast and slow Pointers to n for traversal; 2. 2. Recursion; 3, iterations,

## 2021.03.09

### No.82 Remove duplicate element II from a sorted list

Given a collated list, remove all nodes with duplicate numbers, leaving only the original list with non-recurring numbers.

Example 1:

Input: 1->2->3->3->4->4->5 Output: 1->2->5 Example 2:

Input: 1->1->2->3 Output: 2->3

#### Solution:

``````/* * @lc app=leetcode.cn id=82 lang=javascript * * [82] Remove duplicate elements from sorted lists II */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {ListNode}* /
var deleteDuplicates = function (head) {
let h = p = new ListNode(head),
while (q && q.next) {
if ( q.val == q.next.val) {
while(q.next && q.val == q.next.val) q = q.next;
p.next = q.next;
} else {
p = p.next;
}
q = q.next;
}
return h.next;
};
Copy the code``````

Double pointer processing, need to pay attention to the boundary processing

## 2021.03.10

### Remove duplicate elements from a sorted list

Given a collated list, remove all duplicate elements so that each element appears only once.

Example 1:

Input: 1->1->2 Output: 1->2 Example 2:

Input: 1->1->2->3->3 Output: 1->2->3

#### Solution a:

``````/* * @lc app=leetcode.cn id=83 lang=javascript * * [83] Remove duplicate elements from sorted lists */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {ListNode}* /

let h = p = new ListNode(head),

while(q && q.next) {
if(q.next.val == q.val) {
while(q.next && q.next.val == q.val) {
q = q.next;
}
p.next = q;
}
p = p.next;
q = q.next;
};

return h.next;
};
Copy the code``````

#### Scheme 2:

``````/* * @lc app=leetcode.cn id=83 lang=javascript * * [83] Remove duplicate elements from sorted lists */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {ListNode}* /

}

};
Copy the code``````

1. Fast pointer or single pointer traversal can be used. 2, the recursion

## 2021.03.11

### No.237 Delete a node from the linked list

Write a function that removes a given (non-trailing) node from a linked list. The only argument passed to the function is the node to be deleted.

There is a linked list — head = [4,5,1,9], which can be expressed as:

Example 1:

Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: Given a second node in your list with value 5, after calling your function, the list strain is 4 -> 1 -> 9. Example 2:

Input: head = [4,5,1,9], node = 1 Output: [4,5,9]

Tip:

A linked list contains at least two nodes. All nodes in a linked list have unique values. The given node is a non-trailing node and must be a valid node in the list. Do not return any results from your function.

#### Solution:

``````/* * @lc app=leetcode.cn id=237 lang=javascript * * [237] Delete node from list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} node
* @return {void} Do not return anything, modify node in-place instead.
*/
var deleteNode = function(node) {
if(! node)return null;

node.val = node.next.val;
node.next = node.next.next;
};
Copy the code``````

There is no way to delete a node from the head node. Instead, you need to replace the current value and then delete the next node value

## Conclusion:

1. The most common scheme to delete nodes is the traversal deletion of fast and slow Pointers, the exploration of fast Pointers, and the control of slow Pointers as the final return path of the linked list.
2. You can also use the extra space of recursion, iteration, stack, etc., in exchange for the corresponding time efficiency

## 2021.03.15

Given a linked list, determine whether there are rings in the list.

If there is a node in the list that can be reached again by continuously tracing the next pointer, there is a loop in the list. To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list. Note: POS is not passed as a parameter, only to identify the actual condition of the linked list.

Returns true if there is a loop in the list. Otherwise, return false.

Can you solve this problem with O(1) (i.e., constant) memory?

Example 1:

Input: head = [3,2,0,-4], pos = 1 output: true Example 2:

Input: head = [1,2], pos = 0 output: true explanation: there is a loop in the list with the end connected to the first node. Example 3:

Input: head = [1], pos = -1 Output: false Description: There is no loop in the linked list.

Tip:

The number of nodes in the list ranges from [0, 104] -105 <= node. val <= 105 pos is -1 or a valid index in the list.

#### Solution a:

``````/* * @lc app=leetcode.cn id=141 lang=javascript * * [141] Ring list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
* @return {boolean}* /
let hash = new Map(a);while(head) {
}

return false;
};
Copy the code``````

#### Scheme 2:

``````/* * @lc app=leetcode.cn id=141 lang=javascript * * [141] Ring list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
* @return {boolean}* /
while (fast) {
if (fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
};
Copy the code``````

#### Solution 3:

``````/* * @lc app=leetcode.cn id=141 lang=javascript * * [141] Ring list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
* @return {boolean}* /
try {
return false
} catch {
return true}};Copy the code``````

There are three solutions: 1. Construct hash table; 2. 2, fast pointer judgment; 3. Take advantage of json.stringify’s non-circular reference

## 2021.04.26

Write a program to find the starting node where two singly linked lists intersect. Here are two linked lists:

It intersects at node C1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Reference of the node with value = 8 Input description: The value of the intersecting node is 8. Starting from their respective table heads, list A is [4,1,8,4,5] and list B is [5,0,1,8,4,5]. In A, there are two nodes before the intersection node; In B, there are three nodes before the intersection node.

Example 2:

IntersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Reference of the node with value = 2 Input description: The value of the intersecting node is 2. Counting from the respective table headers, list A is [0,9,1,2,4] and list B is [3,2,4]. In A, there are three nodes before the intersection node; In B, there is 1 node before the intersection node.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Starting from their respective table headers, list A is [2,6,4] and list B is [1,5]. Since these two linked lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so null is returned.

Note:

If two lists do not intersect, null is returned. After the result is returned, the two lists must retain their original structure. It can be assumed that there are no loops in the entire list structure. The program tries to meet the O(n) time complexity and only uses O(1) memory.

#### Solution a:

``````/* * @lc app=leetcode.cn id=160 lang=javascript * * [160] Intersect list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} headA
* @return {ListNode}* /

while (pA) {

while (pB) {
if (pA === pB) returnpA; pB = pB.next; } pA = pA.next; }};Copy the code``````

#### Scheme 2:

``````/* * @lc app=leetcode.cn id=160 lang=javascript * * [160] Intersect list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} headA
* @return {ListNode}* /

const hashmap = new Map(a);let pA = headA;
while (pA) {
hashmap.set(pA, 1);
pA = pA.next;
}

while (pB) {
if (hashmap.has(pB)) returnpB; pB = pB.next; }};Copy the code``````

#### Solution 3:

``````/* * @lc app=leetcode.cn id=160 lang=javascript * * [160] Intersect list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} headA
* @return {ListNode}* /

while(pA ! = pB) { pA = pA ===null ? headB : pA.next;
pB = pB === null ? headA : pB.next;
}

return pA;
};
Copy the code``````

#### Plan 4:

``````/* * @lc app=leetcode.cn id=160 lang=javascript * * [160] Intersect list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} headA
* @return {ListNode}* /
let aNum = 0
let bNum = 0
while (short) {
aNum += 1
short = short.next
}
while (long) {
bNum += 1
long = long.next
}
if (aNum > bNum) {
let dig = aNum - bNum
for (let i = 0; i < dig; i++) {
tempA = tempA.next
}
while (tempA) {
if(tempA == tempB) {
return tempA
} else {
tempA = tempA.next
tempB = tempB.next
}
}
}
if (aNum < bNum) {
let dig = bNum - aNum
for (let i = 0; i < dig; i++) {
tempB = tempB.next
}
while (tempA) {
if(tempA == tempB) {
return tempA
} else {
tempA = tempA.next
tempB = tempB.next

}
}
}
if (aNum = bNum) {
while (tempA) {
if(tempA == tempB) {
return tempA
} else {
tempA = tempA.next
tempB = tempB.next

}
}
}
};
Copy the code``````

There are four solutions: 1. Let A find B; 2. 2. Iterate over the hash table first and then judge. 3, form a cross ring linked list, cross traversal; 4, first go through the longest table, let the longest table go first and then synchronous judgment

## 2021.04.27

### No.142 Circular Linked List II

Given a linked list, return the first node where the list started to enter the loop. Null is returned if the list is loopless. To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list. Note that pos is only used to identify the ring case and is not passed as an argument to the function.

Note: Modifications to the given list are not allowed.

Can you use O(1) space to solve this problem?

Example 1:

Input: head = [3,2,0,-4], pos = 1 output: return list node with index 1 Example 2:

Input: head = [1,2], pos = 0 output: return list node with index 0 description: there is a loop in the list with the end connected to the first node. Example 3:

Input: head = [1], pos = -1 Output: null is returned.

Tip:

The number of nodes in the list is in the range [0, 104] -105 <= node. val <= 105 Pos is -1 or a valid index in the list

#### Solution a:

``````/* * @lc app=leetcode.cn id=142 lang=javascript * * [142] Ring list II */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
* @return {ListNode}* /
let hash = new Map(a);while(head) {
}

return null;
};
Copy the code``````

#### Scheme 2:

``````/* * @lc app=leetcode.cn id=142 lang=javascript * * [142] Ring list II */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
* @return {ListNode}* /
return null;
}
while(fast ! = =null) {
slow = slow.next;
if(fast.next ! = =null) {
fast = fast.next.next;
} else {
return null;
}
if (fast === slow) {
while(ptr ! == slow) { ptr = ptr.next; slow = slow.next; }returnptr; }}return null;
};
Copy the code``````

There are two schemes: 1. Use map or set data structure to record the linked list, and the space complexity is O(N); 2. 2. Use the fast and slow pointer to calculate the encounter distance, which saves the storage space of data structure, and the space complexity is O(1).

## 2021.05.10

### No.143 Rearranges the list

Given a single linked list L: L0→L1→… L0→Ln→L1→ L-1 →L2→ L-2 →…

You can’t just change the values inside a node, but actually switch nodes.

Example 1:

Given a linked list 1->2->3->4, rearrange it as 1->4->2->3. Example 2:

Given a linked list 1->2->3->4->5, rearrange it as 1->5->2->4->3.

#### Solution a:

``````/* * @lc app=leetcode.cn id=143 lang=javascript * * [143] Reorder list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
*/
// Flip the list
const reverseList = head= > {
let pre = null;
while(cur ! = =null) {let temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
// Split the list
const spliceList = head= > {
let dummy = new ListNode(0);

let slow = dummy;
let quick = dummy;

while (quick && quick.next) {
slow = slow.next;
quick = quick.next;
quick = quick.next;
}

let right = slow.next;
slow.next = null;
let left = dummy.next;

return {
left,
right,
dummy
}
}

let { left, right, dummy } = spliceList(head);

right = reverseList(right);

while (left && right) {
let lNext = left.next;
let rNext = right.next;
right.next = left.next;
left.next = right;
left = lNext;
right = rNext;
}

return dummy.next
};
Copy the code``````

#### Scheme 2:

``````/* * @lc app=leetcode.cn id=143 lang=javascript * * [143] Reorder list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
*/
let list = []; // Use arrays to store lists
let node = head; // Use node to traverse the list

// Iterate over the list, storing each element in the array
while (node) {
list.push(node);
node = node.next;
}

let i = 0; // Use the I pointer to iterate through the list from the beginning
let j = list.length - 1; // Use the j pointer to traverse the list from back to front

// The two Pointers advance to the center until they meet
while (i < j) {
// Point I to j and move I back one bit
list[i++].next = list[j];
// Point j to I and move j forward one bit
list[j--].next = list[i];
}
// List [I]. Next needs to be set to null, otherwise the list will ring
list[i].next = null;

};
Copy the code``````

There are two schemes: 1, the fast and slow pointer to split the left and right linked list, using the left and right linked list insertion synthesis new list; 2, use the array position to merge processing

## 2021.05.11

Given the head node of the list, arrange it in ascending order and return the sorted list. Advanced:

Can you sort a list in order n log n time and constant space?

Example 1:

Input: head = [4,2,1,3] output: [1,2,3,4]

Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5] Example 3:

Tip:

The number of nodes in the list is in the range [0, 5 * 104] -105 <= node. val <= 105

#### Solution a:

``````/* * @lc app=leetcode.cn id=148 lang=javascript * * [148] Sort list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {ListNode}* /
// Turn the list into an array
const  list2Arr = head= > {
}
// Turn the array to a linked list
const arr2List = arr= > {
if(arr.length == 0) return null;
for(let i=1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
};
};
// Reorder the array
const sortArr = arr= > {
return arr.sort((a,b) = > a-b)
}

};
Copy the code``````

#### Scheme 2:

``````/* * @lc app=leetcode.cn id=148 lang=javascript * * [148] Sort list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {ListNode}* /
let preSlow = null;
while (fast && fast.next) {
preSlow = slow;
slow = slow.next;
fast = fast.next.next;
}
preSlow.next = null;
const r = sortList(slow);
const merge = (l1, l2) = > {
const dummy = new ListNode(0);
let prev = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
if (l1) prev.next = l1;
if (l2) prev.next = l2;
return dummy.next;
};
return merge(l, r);
};
Copy the code``````

There are two options: 1, the array operation, using the built-in sort sort; 2, merge sort, fast pointer implementation

## 2021.05.12

Please determine whether a linked list is a palindrome list. Example 1:

Input: 1->2 Output: false Example 2:

Input: 1->2->2->1 Output: true Advanced: can you solve this problem with O(n) time complexity and O(1) space complexity?

#### Solution a:

``````/* * @lc app=leetcode.cn id=234 lang=javascript * * [234] Palindrome list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {boolean}* /
// Flip the list
const reverseList = head= > {
let pre=null;
while(cur ! = =null) {let temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
return pre;
}

// Split the list
const splitList = head= > {
while(fast.next ! = =null&& fast.next.next ! = =null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}

if (head == null) return true;

while( l ! = =null&& _l ! = =null ) {
if(l.val ! == _l.val) {return false;
}
l = l.next;
_l = _l.next;
}

return true;
};
Copy the code``````

#### Scheme 2:

``````/* * @lc app=leetcode.cn id=234 lang=javascript * * [234] Palindrome list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {boolean}* /
let a=' ',b=' ';
}
return a===b;
};
Copy the code``````

#### Solution 3:

``````/* * @lc app=leetcode.cn id=234 lang=javascript * * [234] Palindrome list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {boolean}* /
const vals = [];
}
for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
if(vals[i] ! == vals[j]) {return false; }}return true;
};
Copy the code``````

There are three schemes: 1. Use the fast and slow pointer to get the second half of the linked list to flip and compare; 2, using the js plus feature, to achieve a similar stack operation; 3, the use of arrays to reverse the comparison of arrays

## 2021.05.13

Given a single linked list, put all the odd and even nodes together separately. Note that the odd and even nodes here refer to the parity of the node number, not the parity of the node’s value. Try using the in-place algorithm. Your algorithm should have a space complexity of O(1) and a time complexity of O(Nodes), nodes being the total number of nodes.

Example 1:

Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL output: 1 – > 3 – > 5 – > 4 – > 2 – > NULL example 2:

Input: 1 – > 2 – > 3 – > 5 – > 4 – > 7-6 – > > NULL output: 2 – > 3 – > 6-7-1 – > > > 5 – > 4 – > NULL:

The relative order of odd and even nodes should be maintained. The first node of the list is treated as odd, the second as even, and so on.

#### Solution:

``````/* * @lc app=leetcode.cn id=328 lang=javascript * * [328] Odd-even list */

// @lc code=start
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {ListNode}* /

tmp = q;

while(q && q.next) {
p.next = p.next.next;
q.next = q.next.next;
p = p.next;
q = q.next;
}

p.next = tmp;