做模版网站,湖北省京山县建设局网站,网站中加入地图,小兽wordpress编辑器一、题目 已知一个链表的头部head#xff0c;每k个结点为一组#xff0c;按组翻转。要求返回翻转后的头部
k是一个正整数#xff0c;它的值小于等于链表长度。如果节点总数不是k的整数倍#xff0c;则剩余的结点保留原来的顺序。示例如下#xff1a;
#xff08;要求不…一、题目 已知一个链表的头部head每k个结点为一组按组翻转。要求返回翻转后的头部
k是一个正整数它的值小于等于链表长度。如果节点总数不是k的整数倍则剩余的结点保留原来的顺序。示例如下
要求不可以仅仅改变节点内部的值而是真正的交换节点 二、解题思路 1.首先每次检查剩余未翻转的节点是否满足k个如果不满足则直接返回。 2.如果满足k个将其取出写一个独立函数对其翻转并返回翻转后的头尾指针。 3.再根据头尾指针将子表连接回原表中继续往下重复步骤1。
注意在取出子表之前需保存好它在原表中的头尾指针这样翻转后才能连接回原表
三、代码
#include iostreamusing 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;
}//翻转链表并返回头尾
pairListNode*, 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;pairListNode*, 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;
}
四、执行结果
