算法 定长按组翻转链表

一、题目

        已知一个链表的头部head，每k个结点为一组，按组翻转。要求返回翻转后的头部

k是一个正整数，它的值小于等于链表长度。如果节点总数不是k的整数倍，则剩余的结点保留原来的顺序。示例如下：

（要求不可以仅仅改变节点内部的值，而是真正的交换节点）

二、解题思路

        1.首先每次检查剩余未翻转的节点是否满足k个，如果不满足，则直接返回。

        2.如果满足k个，将其取出，写一个独立函数对其翻转，并返回翻转后的头尾指针。

        3.再根据头尾指针，将子表连接回原表中，继续往下重复步骤1。

（注意：在取出子表之前，需保存好它在原表中的头尾指针，这样翻转后才能连接回原表）

三、代码

#include <iostream>using namespace std;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) {}
};//展示链表节点顺序
void showList(ListNode* head) {bool first = true;while (head) {if (first) {first = false;cout << head->val;} else {cout << " -> " << head->val;}head = head->next;}cout << endl;
}//创造链表
ListNode* createList(int count) {ListNode* head = new ListNode(1);ListNode* p = head;for (int i = 2; i <= count; i++) {p->next = new ListNode(i);p = p->next;}p->next = nullptr;return head;
}//翻转链表，并返回头尾
pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {ListNode* prev = tail->next;ListNode* p = head;while (prev != tail) {ListNode* next = p->next;p->next = prev;prev = p;p = next;}return { tail, head };
}//按k个为一组翻转链表
ListNode* reverseKGroup(ListNode* head, int k) {//做一个头节点ListNode* hair = new ListNode(0);hair->next = head;ListNode* pre = hair;while (head != nullptr) {ListNode* tail = pre;//判断剩余节点是否够k个for (int i = 0; i < k; i++) {tail = tail->next;if (!tail) {return hair->next;}}ListNode* next = tail->next;pair<ListNode*, ListNode*> res = myReverse(head, tail);head = res.first;tail = res.second;//将翻转后的子链表接回去pre->next = head;tail->next = next;//准备下一组翻转pre = tail;head = tail->next;}return hair->next;
}//主函数
int main() {ListNode* head = createList(5);cout << "Before reverse by 2 : " << endl;showList(head);//按2个为一组翻转链表ListNode* rev_head = reverseKGroup(head, 2);cout << endl << endl;cout << "Before reverse by 2 : " << endl;showList(rev_head);return 0;
}

四、执行结果