LeetCode 0025 - Reverse Nodes in k-Group
# Hints
- 链表 + 模拟
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Given a linked list, reverse the nodes of a linked list at a time and return its modified list.
is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of then left-out nodes in the end should remain as it is.
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
Note:
Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.
# 题意
给定一个链表,假想将链表中的节点从头到尾按每 个节点一组划分,要求将每一组节点反转顺序。如果最后不足 个节点则保持不变。
# 题解
本题是LeetCode 0024的加强版,仍是按题意模拟即可,但是难度明显大幅提高了,且细节也更加复杂。
事实上LeetCode 0024只是相当于本题中 的情况。但是这仍然很有参考价值,容易发现这相当于仅有边界的情况,我们已经解决了边界处理的问题。
首先,我们考虑实现对一组一组节点的循环操作。具体地讲,我们可以维护 指针和 指针,其中 指向当前一组节点的首个节点的前继节点, 指向当前一组节点的末尾节点。每当处理完一组节点后,将 和 递进即可。
其次,我们考虑实现对每一组内节点的指针更新操作。我们可以维护 两个指针,具体的指针操作过程如下:
初始时,令
p = prv->next
和q = prv->next->next
。首先考虑边界问题,令
p->next = lst->next
和prv->next = lst
。这和LeetCode 0024中对 和 的操作相同。其次考虑循环操作,具体过程如下图所示,不断重复该过程直到
p == lst
为止,然后将 和 递进。
# AC代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode * reverseKGroup(ListNode * head, int k) {
// ����
if (head == nullptr) {
return head;
}
if (k == 1) {
return head;
}
// ����ͷ�ڵ�
ListNode ss = ListNode(0);
ListNode * head0 = &ss;
head0->next = head;
// ��ѭ��
ListNode * prv = head0;
ListNode * lst = prv;
while (prv != nullptr) {
// ��ȡһ���β��
for (int i = 0; i < k; i ++) {
lst = lst->next;
if (lst == nullptr) {
return head0->next;
}
}
// ����һ��
ListNode * p = prv->next;
ListNode * q = prv->next->next;
ListNode * nprv = p;
// ����һ�����β����
p->next = lst->next;
prv->next = lst;
// ����һ����м䲿��
while (p != lst) {
// ����
ListNode * t = q->next;
q->next = p;
// �ݽ�
p = q;
q = t;
}
// �ݽ�
prv = nprv;
lst = prv;
}
// ����
return head0->next;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01