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) {
if(! head)return null;
let p = phead = new ListNode(null);
p.next = head;
while(p.next) {
if(p.next.val == val) {
p.next = p.next.next;
} else{ p = p.next; }}return phead.next;
};
Copy the codeThe 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
Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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) {
let p = head, q = head, m = phead = new ListNode(head);
m.next = head;
// Change the q pointer to q = head.next··· Next has n next
for( let _n = n; _n > 0; _n-- ) {
q = head.next;
head = head.next;
};
// 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;
return phead.next;
};
Copy the codeScheme 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) = > {
if(! head) {return null;
}
const next = recursion(head.next);
lastN++;
if (lastN === n) {
head = next;
}
if (lastN === n + 1) {
head.next = next;
}
return head;
};
return recursion(head);
};
Copy the codeSolution 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) {
const nowHead = [head];
let tempHead = head;
while (tempHead.next) {
nowHead.push(tempHead.next);
tempHead = tempHead.next;
}
let lastN = 0;
let isHead = true;
while (nowHead.length) {
lastN++;
const now = nowHead.pop();
if (lastN - 1 === n) {
isHead = false; now.next = now.next.next; }}if (isHead) {
head = head.next;
}
return head;
};
Copy the codeThere 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
Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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) {
if(! head)return null;
let h = p = new ListNode(head),
q = head;
h.next = head;
p.next = 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 codeDouble 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
Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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}* /
var deleteDuplicates = function(head) {
if(! head)return null;
let h = p = new ListNode(head),
q = head;
h.next = head;
p.next = 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 codeScheme 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}* /
var deleteDuplicates = function(head) {
if(! head || ! head.next)return head;
head.next = deleteDuplicates(head.next);
if(head.next.val == head.val) {
head.next = head.next.next;
}
return head;
};
Copy the code1. 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.
Source: LeetCode link: leetcode-cn.com/problems/de… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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 codeThere 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:
- 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.
- You can also use the extra space of recursion, iteration, stack, etc., in exchange for the corresponding time efficiency
Four, special linked list
2021.03.15
No.141 Circular Linked list
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.
Advanced:
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.
Source: LeetCode link: leetcode-cn.com/problems/li… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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}* /
var hasCycle = function(head) {
if(! head)return false;
let hash = new Map(a);while(head) {
if(hash.has(head)) return true;
hash.set(head, true);
head = head.next;
}
return false;
};
Copy the codeScheme 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}* /
var hasCycle = function(head) {
let fast = head;
let slow = head;
while (fast) {
if (fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
};
Copy the codeSolution 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}* /
var hasCycle = function(head) {
try {
JSON.stringify(head)
return false
} catch {
return true}};Copy the codeThere 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
No.160 Intersecting Linked lists
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.
Source: LeetCode link: leetcode-cn.com/problems/in… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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
* @param {ListNode} headB
* @return {ListNode}* /
var getIntersectionNode = function (headA, headB) {
if(! headA || ! headB)return null;
let pA = headA;
while (pA) {
let pB = headB;
while (pB) {
if (pA === pB) returnpA; pB = pB.next; } pA = pA.next; }};Copy the codeScheme 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
* @param {ListNode} headB
* @return {ListNode}* /
var getIntersectionNode = function (headA, headB) {
if(! headA || ! headB)return null;
const hashmap = new Map(a);let pA = headA;
while (pA) {
hashmap.set(pA, 1);
pA = pA.next;
}
let pB = headB;
while (pB) {
if (hashmap.has(pB)) returnpB; pB = pB.next; }};Copy the codeSolution 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
* @param {ListNode} headB
* @return {ListNode}* /
var getIntersectionNode = function (headA, headB) {
if(! headA || ! headB)return null;
let pA = headA,
pB = headB;
while(pA ! = pB) { pA = pA ===null ? headB : pA.next;
pB = pB === null ? headA : pB.next;
}
return pA;
};
Copy the codePlan 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
* @param {ListNode} headB
* @return {ListNode}* /
var getIntersectionNode = function (headA, headB) {
let aNum = 0
let bNum = 0
let short = headA
let long = headB
let tempA = headA
let tempB = headB
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 codeThere 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.
Advanced:
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
Source: LeetCode link: leetcode-cn.com/problems/li… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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}* /
var detectCycle = function(head) {
if(! head)return null;
let hash = new Map(a);while(head) {
if(hash.has(head)) return head;
hash.set(head);
head = head.next;
}
return null;
};
Copy the codeScheme 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}* /
var detectCycle = function(head) {
if (head === null) {
return null;
}
let slow = head, fast = head;
while(fast ! = =null) {
slow = slow.next;
if(fast.next ! = =null) {
fast = fast.next.next;
} else {
return null;
}
if (fast === slow) {
let ptr = head;
while(ptr ! == slow) { ptr = ptr.next; slow = slow.next; }returnptr; }}return null;
};
Copy the codeThere 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.
Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function(head) {
// Flip the list
const reverseList = head= > {
let cur = 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);
dummy.next = head;
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 codeScheme 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
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function(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;
// Head is also the head node of the new list
return head;
};
Copy the codeThere 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
No.148 Sorted linked lists
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:
Input: head = []
Tip:
The number of nodes in the list is in the range [0, 5 * 104] -105 <= node. val <= 105
Source: LeetCode link: leetcode-cn.com/problems/so… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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}* /
var sortList = function(head) {
// Turn the list into an array
const list2Arr = head= > {
if(! head)return [];
const a = [head.val];
while(head.next) {a.push(head.next.val); head = head.next; }return a;
}
// Turn the array to a linked list
const arr2List = arr= > {
if(arr.length == 0) return null;
let head = new ListNode(arr[0]);
let cur = head;
for(let i=1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
};
return head;
};
// Reorder the array
const sortArr = arr= > {
return arr.sort((a,b) = > a-b)
}
return arr2List(sortArr(list2Arr(head)))
};
Copy the codeScheme 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}* /
var sortList = function(head) {
if(! head || ! head.next)return head;
let slow = head, fast = head;
let preSlow = null;
while (fast && fast.next) {
preSlow = slow;
slow = slow.next;
fast = fast.next.next;
}
preSlow.next = null;
const l = sortList(head);
const r = sortList(slow);
// Merge linked list functions
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 codeThere are two options: 1, the array operation, using the built-in sort sort; 2, merge sort, fast pointer implementation
2021.05.12
No.234 Palindrome linked list
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?
Source: LeetCode link: leetcode-cn.com/problems/pa… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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}* /
var isPalindrome = function(head) {
// Flip the list
const reverseList = head= > {
let cur=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= > {
let fast = head;
let slow = head;
while(fast.next ! = =null&& fast.next.next ! = =null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
if (head == null) return true;
let l = head;
let _l = reverseList(splitList(head).next);
while( l ! = =null&& _l ! = =null ) {
if(l.val ! == _l.val) {return false;
}
l = l.next;
_l = _l.next;
}
return true;
};
Copy the codeScheme 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}* /
var isPalindrome = function(head) {
let a=' ',b=' ';
while(head! =null){
a=a+head.val;
b=head.val+b;
head=head.next;
}
return a===b;
};
Copy the codeSolution 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}* /
var isPalindrome = function(head) {
const vals = [];
while(head ! = =null) {
vals.push(head.val);
head = head.next;
}
for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
if(vals[i] ! == vals[j]) {return false; }}return true;
};
Copy the codeThere 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
No.328 Parity linked list
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.
Source: LeetCode link: leetcode-cn.com/problems/od… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
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}* /
var oddEvenList = function(head) {
if(! head)return null;
let p = head,
q = head.next,
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;
return head;
};
Copy the codeUsing double pointer to split processing
Conclusion:
- Special list of the most common scheme is fast and slow pointer related to the list search and processing, and then according to the form of special list requirements for split and combination;
- Additional data structures such as stacks and hash tables can also be used for processing
