Original link: leetcode-cn.com/problems/re…
Answer:
Can first refer to the official problem solution, and then look at this problem solution.
The general idea is as follows:
- Split a linked list into N sublists, each with K nodes.
- Flip each sublist individually.
- Join the flipped child list to the front and back nodes.
- Note that the linked list is null and the total number of linked list nodes is not an integer multiple of K.
If writing the entire code at once is difficult, we can solve the problem step by step:
- Write the circular linked list method
/ * * *@param {ListNode} head
* @param {number} k
* @return {ListNode}* /
var reverseKGroup = function (head, k) {
// Reverse rotor linked list method, based on 206. Reverse rotor linked list, can refer to the following problem:
// https://leetcode-cn.com/problems/reverse-linked-list/solution/206-fan-zhuan-lian-biao-javascriptwhilexun-huan-di/
function reverseNode(head, tail) {
// This will be added in step 2
}
// Create dummy node as prevNode for first traversal of the list
// dummyNode does not participate in list traversal, which means that its next point is always the head of the list
let dummyNode = new ListNode(-1);
dummyNode.next = head;
// Assign dummyNode to prevNode for the list traversal.
// prevNode moves over time.
// On the first pass, prevNode.next points to the flipped list head node.
// The direction of dummyNode.next will be changed at the same time.
let prevNode = dummyNode;
while (head) {
// Create a tail node, which will be moved k bits and end up pointing to the pseudo-node of the current child list.
let tail = prevNode;
// Move tail to the end of the current child list and check whether the length of the remaining nodes is >=k
for (let i = 0; i < k; i++) {
// Step 3
}
NextNode is the head node of the next sublist
let nextNode = tail.next;
// Invert the child list to return its new head and tail nodes for the connecter list
[head, tail] = reverseNode(head, tail);
// Link the parent list to the child list
prevNode.next = head;
tail.next = nextNode;
// Move the prevNode and head forward to continue the loop for the next sublist
prevNode = tail;
head = tail.next;
}
// dummyNode refers to the head node of the list, and dummyNode.next is the flipped list output.
// If head is null, the while loop is returned directly
return dummyNode.next;
};
Copy the code- Added anti-rotor linked list method
/ * * *@param {ListNode} head
* @param {number} k
* @return {ListNode}* /
var reverseKGroup = function (head, k) {
// Reverse rotor linked list method, based on 206. Reverse rotor linked list, can refer to the following problem:
// https://leetcode-cn.com/problems/reverse-linked-list/solution/206-fan-zhuan-lian-biao-javascriptwhilexun-huan-di/
function reverseNode(head, tail) {
// If the sublist has been reversed, the node after that reversal is the next node in the current sublist.
// So just sign a node to tail.next
let prevNode = tail.next;
// Cache the head, using node to traverse the sublist and reverse it.
// Since the head pointer cannot be changed, it needs to be used to return the inverted end.
let node = head;
PrevNode moves to tail to indicate that the child list is reversed.
while(prevNode ! == tail) {const tempNode = node.next;
node.next = prevNode;
prevNode = node;
node = tempNode;
}
// After the inversion is complete, the original head and tail nodes have been switched, and the reverse is returned.
// Note that the head and tail nodes are not actually changed, but their positions are reversed because the sublist has been reversed.
return [tail, head];
}
// Create dummy node as prevNode for first traversal of the list
// dummyNode does not participate in list traversal, which means that its next point is always the head of the list
let dummyNode = new ListNode(-1);
dummyNode.next = head;
// Assign dummyNode to prevNode for the list traversal.
// prevNode moves over time.
// On the first pass, prevNode.next points to the flipped list head node.
// The direction of dummyNode.next will be changed at the same time.
let prevNode = dummyNode;
while (head) {
// Create a tail node, which will be moved k bits and end up pointing to the pseudo-node of the current child list.
let tail = prevNode;
// Move tail to the end of the current child list and check whether the length of the remaining nodes is >=k
for (let i = 0; i < k; i++) {
// Step 3
}
NextNode is the head node of the next sublist
let nextNode = tail.next;
// Invert the child list to return its new head and tail nodes for the connecter list
[head, tail] = reverseNode(head, tail);
// Link the parent list to the child list
prevNode.next = head;
tail.next = nextNode;
// Move the prevNode and head forward to continue the loop for the next sublist
prevNode = tail;
head = tail.next;
}
// dummyNode refers to the head node of the list, and dummyNode.next is the flipped list output.
// If head is null, the while loop is returned directly
return dummyNode.next;
};
Copy the code- Check whether the length of the remaining nodes is greater than or equal to K
/ * * *@param {ListNode} head
* @param {number} k
* @return {ListNode}* /
var reverseKGroup = function (head, k) {
// Reverse rotor linked list method, based on 206. Reverse rotor linked list, can refer to the following problem:
// https://leetcode-cn.com/problems/reverse-linked-list/solution/206-fan-zhuan-lian-biao-javascriptwhilexun-huan-di/
function reverseNode(head, tail) {
// If the sublist has been reversed, the node after that reversal is the next node in the current sublist.
// So just sign a node to tail.next
let prevNode = tail.next;
// Cache the head, using node to traverse the sublist and reverse it.
// Since the head pointer cannot be changed, it needs to be used to return the inverted end.
let node = head;
PrevNode moves to tail to indicate that the child list is reversed.
while(prevNode ! == tail) {const tempNode = node.next;
node.next = prevNode;
prevNode = node;
node = tempNode;
}
// After the inversion is complete, the original head and tail nodes have been switched, and the reverse is returned.
// Note that the head and tail nodes are not actually changed, but their positions are reversed because the sublist has been reversed.
return [tail, head];
}
// Create dummy node as prevNode for first traversal of the list
// dummyNode does not participate in list traversal, which means that its next point is always the head of the list
let dummyNode = new ListNode(-1);
dummyNode.next = head;
// Assign dummyNode to prevNode for the list traversal.
// prevNode moves over time.
// On the first pass, prevNode.next points to the flipped list head node.
// The direction of dummyNode.next will be changed at the same time.
let prevNode = dummyNode;
while (head) {
// Create a tail node, which will be moved k bits and end up pointing to the pseudo-node of the current child list.
let tail = prevNode;
// Move tail to the end of the current child list and check whether the length of the remaining nodes is >=k
for (let i = 0; i < k; i++) {
// Move the tail pointer back
// Check whether it is empty or not
tail = tail.next;
// If tail is null, there are less than k links left in the list
if(! tail) {returndummyNode.next; }}NextNode is the head node of the next sublist
let nextNode = tail.next;
// Invert the child list to return its new head and tail nodes for the connecter list
[head, tail] = reverseNode(head, tail);
// Link the parent list to the child list
prevNode.next = head;
tail.next = nextNode;
// Move the prevNode and head forward to continue the loop for the next sublist
prevNode = tail;
head = tail.next;
}
// dummyNode refers to the head node of the list, and dummyNode.next is the flipped list output.
// If head is null, the while loop is returned directly
return dummyNode.next;
};
Copy the code