C语言实现-K-个一组翻转链表

题目描述

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

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

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

示例：

输入：1->2->3->4->5 当 k = 2 时，输出：2->1->4->3->5 当 k = 3 时，输出：3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

解法思路

这道题可以采用递归的思路来解决。设当前的链表为 list。将 list 分成 head 和 tail 两个链表，其中 head 包含前 k 个节点，tail 则是剩余的节点。

接下来，对 tail 部分继续递归调用 reverseKGroup 函数，返回值为反转后的链表。

最后，将 head 和 tail 部分进行合并，即可得到最终的结果。

具体实现见代码注释。

C 代码

/**

• Definition for singly-linked list.
• struct ListNode {

• int val;
  

• struct ListNode *next;
  

• }; */

struct ListNode* reverseKGroup(struct ListNode* head, int k) { struct ListNode *p = head; int count = 0; // 统计当前链表中节点的个数 while (p && count < k) { p = p->next; count++; } // 如果当前链表中节点的个数小于 k，则不进行翻转操作 if (count < k) { return head; } // 递归调用 reverseKGroup 函数，返回值为反转后的链表 struct ListNode *newHead = reverseKGroup(p, k); struct ListNode *prev = NULL, *cur = head; // 对当前链表进行翻转操作 for (int i = 0; i < k; i++) { struct ListNode *next = cur->next; cur->next = prev; prev = cur; cur = next; } // 将翻转后的链表与递归调用返回的链表进行合并 head->next = newHead; return prev; }