Last Updated: 2023-11-12 13:54:55 Sunday
-- TOC --
又是singly-linked list...还是hard...
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k 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 k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed.
这段英文写的有点不清楚，就是连续k个节点一组，进行反转，不允许使用交换节点值的方式，最后一段如果没有k个节点，就不动。
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Constraints:
- The number of nodes in the list is n.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
题目明确要求不允许采用交换节点值的方法，因为这是个简单的方法，不过不是最简单的，转array才是最简单，只是多用点内容而已。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
knode = []
p = head
n = 0
h = r = ListNode()
while p:
knode.append(p)
n += 1
p = p.next
if n == k:
for node in reversed(knode):
r.next = r = node
knode = []
n = 0
r.next = knode[0] if knode else None
return h.next
这个实现是很清晰的，速度就是\(O(N)\)，N为节点数，每个节点扫描2次而已。唯一的缺点就是多用点内存。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
vector<ListNode*> t;
t.reserve(k);
int n {};
ListNode *p { head };
ListNode h { ListNode{} };
ListNode *r { &h };
while(p){
t.push_back(p);
++n;
p = p->next;
if(n == k){
while(n > 0)
r = r->next = t[--n];
t.clear();
}
}
r->next = (n==0 ? nullptr : t[0]);
return h.next;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
struct ListNode **parr = malloc(sizeof(char*)*k);
int n = 0;
struct ListNode *p = head;
struct ListNode h = {};
struct ListNode *r = &h;
while(p){
parr[n++] = p;
p = p->next;
if(n == k)
while(n > 0)
r = r->next = parr[--n];
}
r->next = (n==0 ? NULL : parr[0]);
free(parr);
return h.next;
}
这复杂的指针操作，反正我是晕了接近一个下午才跑通的...不得不提一个最佳实践，对于single-linked结构，手动增加一个dummy head，可以让代码简化不少。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
p = head
n = 0
k1 = p
nh = r = ListNode()
while p:
n += 1
p = p.next
if n == k:
k2 = k1.next
h = k1
while k2 != p:
k3 = k2.next
k2.next = h
h = k2
k2 = k3
r.next = h
r = k1
k1.next = k1 = p
n = 0
return nh.next
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) noexcept{
int n {};
ListNode dummy_head;
ListNode *r { &dummy_head };
ListNode *p, *k1fix;
p = k1fix = head;
while(p){
++n;
p = p->next;
if(n == k){
ListNode *k2 { k1fix->next };
ListNode *h { k1fix };
while(k2 != p){
ListNode *k3 { k2->next };
k2->next = h;
h = k2;
k2 = k3;
}
r->next = h;
r = k1fix;
k1fix = k1fix->next = k2;
n = 0;
}
}
return dummy_head.next;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
int n = 0;
struct ListNode *p, *k1fix, *h;
p = k1fix = h = head;
struct ListNode dummy_head;
struct ListNode *r = &dummy_head;
while(p){
++n;
p = p->next;
if(n == k){
struct ListNode *k2 = k1fix->next;
h = k1fix;
while(k2 != p){
struct ListNode *k3 = k2->next;
k2->next = h;
h = k2;
k2 = k3;
}
r->next = h;
r = k1fix;
k1fix = k1fix->next = p;
n = 0;
}
}
return dummy_head.next;
}
当你感觉大脑不够用的时候，请用递归训练思维...:)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
n = 0
p = h = head
while p:
n += 1
p = p.next
if n == k:
k2 = h.next
while k2 != p:
k3 = k2.next
k2.next = h
h = k2
k2 = k3
head.next = self.reverseKGroup(p,k)
break
return h
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) noexcept{
int n {};
ListNode *p, *h;
p = h = head;
while(p){
++n;
p = p->next;
if(n == k){
ListNode *k2 { h->next };
while(k2 != p){
ListNode *k3 { k2->next };
k2->next = h;
h = k2;
k2 = k3;
}
head->next = reverseKGroup(p,k);
break;
}
}
return h;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
int n = 0;
struct ListNode *p, *h;
p = h = head;
while(p){
++n;
p = p->next;
if(n == k){
struct ListNode *k2 = h->next;
while(k2 != p){
struct ListNode *k3 = k2->next;
k2->next = h;
h = k2;
k2 = k3;
}
head->next = reverseKGroup(p,k);
break;
}
}
return h;
}
本文链接：https://cs.pynote.net/ag/leetcode/202311031/
-- EOF --
-- MORE --