LeetCode25 Reverse Nodes in k-Group

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5 （Hard）

分析：

题目意思是每k个链表进行翻转，不足k个保持不变。

可以写一个翻转k个节点的辅助函数，然后在原函数中判断后续是否有k个节点，以及后续节点位置。

注意事项见代码注释。

代码：

class Solution {
private:
ListNode* reverseKelement(ListNode* head, int k) {
ListNode* result = nullptr;
for (int i = ; i < k; ++i) {
ListNode* temp = head -> next;
head -> next = result;
result = head;
head = temp;
}
return result;
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr) {
return head;
}
ListNode dummy();
dummy.next = head;
head = &dummy; ListNode* runner = head -> next;
int flag = ;
for (int i = ; i < k; ++i) {
if (runner -> next != nullptr || (runner -> next == nullptr && k == i + ) ) { //恰好k个到结尾情况没考虑，例如[1,2] 2情况
runner = runner -> next;
}
else {
flag = ;
break;
}
}
while (flag == ) {
ListNode* temp1 = head -> next;
head -> next = reverseKelement(temp1, k);
temp1 -> next = runner;
head = temp1;
for (int i = ; i < k; ++i) {
if (runner != nullptr && (runner -> next != nullptr || (runner -> next == nullptr && k == i + )) ) { //对应添加runner != nullptr
runner = runner -> next;
}
else {
flag = ;
break;
}
}
}
return dummy.next;
}
};