2022/1/19 链表 || 25. K 个一组翻转链表
题目地址(25. K 个一组翻转链表labuladong题解https://labuladong.gitee.io/plugin-v3/?qno=25&原题链接https://leetcode-cn.com/problems/reverse-nodes-in-k-group/题目描述给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。k 是一
·
题目地址(25. K 个一组翻转链表
labuladong题解
https://labuladong.gitee.io/plugin-v3/?qno=25&
原题链接
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
题目描述
给你一个链表,每 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]
示例 3:
输入:head = [1,2,3,4,5], k = 1
输出:[1,2,3,4,5]
示例 4:
输入:head = [1], k = 1
输出:[1]
提示:
列表中节点的数量在范围 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz
前置知识
思路
代码
- 语言支持:Java
Java Code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
// class Solution {
// public ListNode reverseKGroup(ListNode head, int k) {
// if (head == null) return null;
// // 区间 [a, b) 包含 k 个待反转元素
// ListNode a, b;
// a = b = head;
// for (int i = 0; i < k; i++) {
// // 不足 k 个,不需要反转,base case
// if (b == null) return head;
// b = b.next;
// }
// // 反转前 k 个元素
// ListNode newHead = reverse(a, b);
// // 递归反转后续链表并连接起来
// a.next = reverseKGroup(b, k);
// return newHead;
// }
// /** 反转区间 [a, b) 的元素,注意是左闭右开 */
// ListNode reverse(ListNode a, ListNode b) {
// ListNode pre, cur, nxt;
// pre = null; cur = a; nxt = a;
// // while 终止的条件改一下就行了
// while (cur != b) {
// nxt = cur.next;
// cur.next = pre;
// pre = cur;
// cur = nxt;
// }
// // 返回反转后的头结点
// return pre;
// }
// }
class Solution{
public ListNode reversrkGroup(ListNode head, in k){
if(head == null){
return null;
}
ListNode a,b;
a=b=head;
for(int i = 0 ;i<k;i++){
if(b==null){
return head;
b=b.next;
}
}
ListNode newHead = reverse(a,b);
a.next = reverseKGroup(b,k);
return newHead;
}
ListNode reverse(a,b){
ListNode cur,pre,nxt;
cur = nxt = a;
pre =null;
while(cur!=b){
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
更多推荐
已为社区贡献1条内容
所有评论(0)