BM3. 链表中的节点每k个一组翻转
描述
示例1
输入:
{1,2,3,4,5},2
输出:
{2,1,4,3,5}
示例2
输入:
{},1
输出:
{}
C++ 解法, 执行用时: 2ms, 内存消耗: 392KB, 提交时间: 2020-09-07
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
ListNode *p=head;
ListNode *new_head=head;
int kk=k;
ListNode *ne=NULL;
ListNode *tail=NULL;
while(p)
{
if(kk==1)
{
ne=p->next;
p->next=NULL;
ListNode *temp=reverse(head);;
if(new_head==head)
new_head=temp;
if(tail)
tail->next=p;
tail=head;
head=ne;
p=ne;
kk=k;
continue;
}
kk--;
p=p->next;
}
if(tail)
tail->next=head;
return new_head;
}
ListNode *reverse(ListNode *start)
{
ListNode * p=nullptr;
while(start)
{
ListNode *temp=start->next;
start->next=p;
p=start;
start=temp;
}
return p;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 416KB, 提交时间: 2021-09-09
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
pair<ListNode*, ListNode*> reverseList(ListNode* head, ListNode* tail)
{
ListNode* pre = tail->next;
ListNode* p = head;
while (pre != tail)
{
ListNode* nex = p->next;
p->next = pre;
pre = p;
p = nex;
}
return { tail, head };
}
ListNode* reverseKGroup(ListNode* head, int k) {
// 模拟法，时O(n)，空O(1)
ListNode* dummy = new ListNode(0); // 伪头节点
dummy->next = head; // head指向每个组的头节点
ListNode* front = dummy; // 前一个指针初始化为伪头节点
while (head != nullptr) // 每次往后挪动head指针，不为空则继续
{
ListNode* tail = front; // 每组的尾指针初始化为组头指针的前一个指针pre
for (int i = 0; i < k; i++) // 判断后续是否还有k个节点
{
tail = tail->next; // 往后移动尾指针k次
if (tail == nullptr) // 若尾指针为空，则说明该组已经不足k个节点
return dummy->next; // 此时满足退出条件，返回伪头节点的下一个节点即可
}
ListNode* back = tail->next; // 每组后一个指针为尾指针的下一个指针
pair<ListNode*, ListNode*> res = reverseList(head, tail);
head = res.first, tail = res.second; // 翻转每组链表后，得到新的头尾指针
// 将翻转后的那组链表重新接回原位置
front->next = head;
tail->next = back;
// 往后移动指针
front = tail;
head = front->next;
}
return dummy->next;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 420KB, 提交时间: 2021-09-09
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
pair<ListNode*,ListNode*> reverse(ListNode* head, ListNode* tail){
ListNode *pre=nullptr;
ListNode *cur=head;
while(pre!=tail){
ListNode *temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return {pre,head};
}
ListNode* reverseKGroup(ListNode* head, int k) {
if(head==nullptr)return nullptr;
// write code here
ListNode Hair(-1);
ListNode *pHair=&Hair;
pHair->next=head;
ListNode *pre=pHair;
while(true){
int step=k;
ListNode *cur=pre;
while(step--){
cur=cur->next;
if(cur==nullptr) return pHair->next;
}
ListNode *nex=cur->next;
auto res=reverse(pre->next,cur);
pre->next=res.first;
res.second->next=nex;
pre=res.second;
}
return pHair->next;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2021-09-10
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
auto p =head;
for(int i =0;i<k;i++){
if(!p)return head;
p=p->next;
}
auto res = reverse(head,p);
auto temp =res;
while(temp->next){
temp=temp->next;
}
temp->next=reverseKGroup(p, k);
return res;
}
ListNode* reverse(ListNode* head,ListNode* b){
ListNode* prev =nullptr;
ListNode* curr = head;
while(curr!=b){
auto next = curr->next;
curr->next = prev;
prev=curr;
curr=next;
}
return prev;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2021-09-09
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
if (head == nullptr || head->next == nullptr) return head;
int length = getLen(head);
int num = length / k;
if (num == 0) return head;
ListNode* dummyHead = new ListNode(0), *now = dummyHead, *cur = head;
for (int i = 0; i < num; ++i) {
ListNode* pre = nullptr;
for (int j = 0; j < k; ++j) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
now->next = pre;
while (pre->next != nullptr) pre = pre->next;
pre->next = cur;
now = pre;
}
return dummyHead->next;
}
private:
int getLen(ListNode* node) {
int cnt = 0;
while (node != nullptr) {
cnt++;
node = node->next;
}
return cnt;
}
};