脚本宝典收集整理的这篇文章主要介绍了25.K个一组翻转链表,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
给你一个链表,每 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
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路 1.从头开始找到一组需要翻转的节点,没找到就直接返回头节点 2.开始翻转,并返回翻转后的头节点 3.对下一轮 k 个节点也进行翻转操作。 4.将上一轮翻转后的尾结点指向下一轮翻转后的头节点,即将每一轮翻转的k的节点连接起来。
递归的终止条件 找到需要反转的k个元素,如果没有找到K个元素,就可以终止递归条件了
if(head==null||head.next==null){
return head;
} //这个判断可以省略,这样最后不足k个元素不用递归到最后一个节点了,直接递归到不满足k个元素一组的头节点就结束了。
ListNode end = head; //记录结尾
for(int i=0;i<k;i++){ //找到需要翻转的k个元素 0,1,2会找三个节点
if(end ==null) return head; //没有找到k个元素,直接返回头节点
end = end.next;
}
本层递归逻辑 找到了k个节点,开始翻转 head 指向链表的第一个节点,end指向下一次准备翻转的头节点,也就是这次翻转链表的结尾节点的下一个节点 将上一轮翻转后的尾结点指向下一轮翻转后的头节点,即将每一轮翻转的k的节点连接起来。
/**
* 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) {
ListNode end = head;
for(int i=0;i<k;i++){ //找到需要翻转的k个元素 0,1,2会找三个节点
if(end ==null) return head; //没有找到k个元素,直接返回头节点
end = end.next;
}
ListNode newHead = reverse(head,end); //这一组先翻转,抽象成函数,是因为还需要利用这一轮的head也就是翻转后的尾节点指向新的头节点
head.next = reverseKGroup(end,k);//下一轮进行翻转
return newHead;
}
ListNode reverse(ListNode head,ListNode end){
ListNode tmp;
ListNode pre=null;
while(head!=end){ //如果end指向要翻转的链表的结尾这个里会少循环一次,所以我们让end指向下一次准备翻转的头节点
tmp = head.next;
head.next = pre;
pre = head;
head=tmp;
} //翻转结束
return pre; //返回翻转后的头节点
}
}
迭代的办法就是一次处理一组节点,
思路 1.从头开始找到一组需要翻转的节点,没找到就直接返回头节点 2.开始翻转,并返回翻转后的头节点 3.对下一轮 k 个节点也进行翻转操作。 4.将上一轮翻转后的尾结点指向下一轮翻转后的头节点,即将每一轮翻转的k的节点连接起来。
最后返回的值是反转后的链表的头节点,我们这里可以加一个节点在最开头,不管怎么反转,最后返回的都是第一个节点.next
/**
* 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) {
ListNode next = null;
ListNode dummy = new ListNode();
dummy.next = head; //添加一个节点放在链表最开头用于最后返回最后的结果
ListNode pre = dummy;
ListNode tail = dummy;
while(head!=null &&head.next != null){
//找到K个一组
for(int i=0;i<k && tail!=null;i++){
tail = tail.next;
}
if(tail==null)break; //说明没有找到,不用反转了之前连接好了,直接返回
ListNode start = pre.next;
next = tail.next;//保存下一个元素,为了反转后可以连上
pre.next = reverse(start,next); //反转节点
start.next = next ;//连接新表
pre = start;
tail = pre;
}
return dummy.next;
}
ListNode reverse(ListNode head,ListNode next){
ListNode tmp;
ListNode pre=null;
while(head!=next){
tmp = head.next;
head.next = pre;
pre = head;
head=tmp;
}
return pre;
}
}
以上是脚本宝典为你收集整理的25.K个一组翻转链表全部内容,希望文章能够帮你解决25.K个一组翻转链表所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。