算法 定长按组翻转链表

一、题目

        已知一个链表的头部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;
}

四、执行结果