leetcode 25. K 个一组翻转链表

大耗子 2021年02月18日 12次浏览

题目:K 个一组翻转链表

25. K 个一组翻转链表

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

示例:

给你这个链表:1->2->3->4->5

k = 2 时,应当返回: 2->1->4->3->5

k = 3 时,应当返回: 3->2->1->4->5

解题思路

例如:1->2->3->4->5->6->7k = 3 时,应当返回: 3->2->1->6->5->4->7

  1. 申请一个结点hair作为前序结点,同时也方便返回链表。将链表作为该结点的后续结点。
  2. 断开end的后续指针。
  3. 然后将start作为起点,翻转链表。此时只会翻转1~3。翻转完成后,pre->next指向end, start->next指向next。重新链接上断开后的链表。
  4. 将pre,start, end,next四个指针重新初始化,指向对应的位置。

链表k翻转

代码

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) {
		if (!head || k == 1 || k == 0) return head;
		ListNode hair(0, head);
		ListNode *start = head, *end = head;
		ListNode *preNode = &hair, *nextNode = NULL;
		while (1) {
			// 步骤一:探测是否满足翻转条件
			end = probe(start, k);
			if (!end) {
				break;
			}
			// 保存下一节的头部
			nextNode = end->next;
			// 步骤二:断开与后一节的链接
			end->next = NULL;
			// 步骤三:翻转并链接结点
			reverse(start);
			// 连接下一节的头部
			start->next = nextNode;
			// 前段结点与翻转的结点连接起来
			preNode->next = end;
			// 步骤四:更新前序结点
			preNode = start;
			// 更新翻转段起始
			start = nextNode;
			end = nextNode;
		}
		return hair.next;
	}
	ListNode* reverse(ListNode* head) {
		ListNode* preNode = NULL, *curNode = head;
		ListNode * nextNode = NULL;
		// 循环翻转所有结点
		while (curNode) {
			nextNode = curNode->next;
			curNode->next = preNode;
			preNode = curNode;
			curNode = nextNode;
		}
		return preNode;
	}
	// 探测是否还有k个结点
	ListNode * probe(ListNode *head, int k) {
        // k个结点只需要前移动k-1次
		while (head && --k) {
			head = head->next;
		}
		return head;
	}
    // 打印函数
	void print(ListNode * res) {
		while (res != NULL)
		{
			cout << res->val << " ";
			res = res->next;
		}
		cout << endl;
	}
};




#define SIZE_TEST 7
int main()
{
	ListNode* head0 = new ListNode(0);
	ListNode* head = head0;
	srand(time(NULL));
	for (int i = 0; i < SIZE_TEST; i++)
	{
		ListNode* mNode = new ListNode(i+1);
		head0->next = mNode;
		head0 = head0->next;
	}
	
	Solution sln;
	ListNode*res = sln.reverseKGroup(head, 3);
    sln.print(res);
	return 0;
}