题目描述

25. K 个一组翻转链表

难度困难1920收藏分享切换为英文接收动态反馈

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

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

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

示例 1：

输入：head = [1,2,3,4,5], k = 2

输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3

输出：[3,2,1,4,5]

提示：

• 链表中的节点数目为 n

• 1 <= k <= n <= 5000

• 0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

递归方法

如果对该代码不清楚可以画图进行理解

核心思想是将k个元素进行反转 利用递归进行循环

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseKGroup(struct ListNode* head, int k)
{//创建是那个指针 s记录反转之后的头节点 e记录反转之后的尾节点 c要反转的下一个节点struct ListNode* ptrStart;struct ListNode* ptrEnd;struct ListNode* ptrCurr;if(head == NULL){return head;}//如果头节点不为空 但所有节点之和不等于k也就不反转 直接返回headptrCurr = head;for(int i = 0;inext;}else{return head;//遇到空就返回头节点}}//将k个元素反转 首先要明白 两个元素进行翻转需要进行1此 以此类推 k个元素 需要k-1次ptrStart = head;ptrEnd = ptrStart;ptrCurr = ptrStart->next;for(int i = 1;inext = ptrCurr->next;ptrCurr->next = ptrStart;ptrStart = ptrCurr;ptrCurr = ptrEnd->next;}}ptrEnd->next = reverseKGroup(ptrCurr,k);//递归 看起来还是挺简洁的return ptrStart;
}

非递归

将链表中的元素放到数组中 将数组中的元素进行反转 再将数组中的元素按照下标与节点的对应关系

将数组值赋值给对应节点

相当于改变链表的值 没有对链表节点进行改变

/*** 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 len = 0;while(p){len++;p = p->next;}int nums[len],i = 0;p = head;while(p){nums[i++] = p->val;p = p->next;}for(i = 0;i + k <= len;i = i + k){int m,n;for(m = i,n = i + k - 1;m < n;m++,n--){int temp = nums[m];nums[m] = nums[n];nums[n] = temp;}}// for(i = 0;i < len;i++){     // 打印//     printf("%d ",nums[i]);// }p = head,i = 0;while(p){p->val = nums[i++];p = p->next;}return head;
}

以上两种方法 都还不错~