当前位置: 首页> 健康> 科研 > Hot100】LeetCode—25. K 个一组翻转链表

Hot100】LeetCode—25. K 个一组翻转链表

时间:2025/7/11 7:37:49来源:https://blog.csdn.net/weixin_44382896/article/details/141348336 浏览次数:0次

目录

  • 1- 思路
    • 双指针 start 和 end + 链表翻转
  • 2- 实现
    • ⭐25. K 个一组翻转链表——题解思路
  • 3- ACM 实现


  • 原题连接:25. K 个一组翻转链表

1- 思路

双指针 start 和 end + 链表翻转

实现思路:

  • 1- 通过 pre指针和 end 指针定位,
    • pre 记录需要翻转的链表的头
    • end 根据 k 和当前 end 不为 null 进行循环遍历
  • 2- 得到 end 之后 进行拆链,拆头和尾
    • 尾:记录下一个起始点
    • 头:拆掉的结点,让它为 null
  • 3- 进行翻转
    • 翻转后更新 prenext,更新 preend

2- 实现

⭐25. K 个一组翻转链表——题解思路

在这里插入图片描述

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummyHead = new ListNode(-1);dummyHead.next = head;// 链表头 和 尾ListNode pre = dummyHead;ListNode end = dummyHead;while(end.next!=null){// 定位 endfor(int i = 0;i<k&& end!=null;i++){end = end.next;}if(end==null){break;}// 断链逻辑ListNode tmp = end.next;ListNode start = pre.next;pre.next = null;end.next = null;pre.next = reverseL(start);start.next = tmp;// 更新pre = start;end = start;}return dummyHead.next;}public ListNode reverseL(ListNode head){if(head==null || head.next==null){return head;}ListNode cur = reverseL(head.next);head.next.next = head;head.next = null;return cur;}
}

3- ACM 实现

public class reverseKGroup {public static class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public static ListNode reverseK(ListNode head,int k){ListNode dummyHead = new ListNode(-1);dummyHead.next = head;ListNode pre = dummyHead;ListNode end = dummyHead;// 2. 遍历// 2.1 遍历条件while(end.next!=null){//2.2定位endfor(int i = 0 ; i < k && end!=null;i++){end = end.next;}if(end == null){break;}// 2.3 断链+翻转ListNode tmp = end.next;ListNode start = pre.next;pre.next = null;end.next = null;pre.next = reverseL(start);start.next = tmp;pre = start;end = start;}return dummyHead.next;}public static ListNode reverseL(ListNode head){if(head==null || head.next==null){return head;}ListNode cur = reverseL(head.next);head.next.next = head;head.next = null;return cur;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);
// 读取第一个链表的节点数量int n1 = sc.nextInt();ListNode head1 = null, tail1 = null;for (int i = 0; i < n1; i++) {int val = sc.nextInt();ListNode newNode = new ListNode(val);if (head1 == null) {head1 = newNode;tail1 = newNode;} else {tail1.next = newNode;tail1 = newNode;}}System.out.println("输入k");int k = sc.nextInt();ListNode forRes = reverseK(head1,k);while(forRes!=null){System.out.print(forRes.val+" ");forRes = forRes.next;}}
}
关键字:Hot100】LeetCode—25. K 个一组翻转链表

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: