【CT】LeetCode手撕—25. K 个一组翻转链表

本文主要是介绍【CT】LeetCode手撕—25. K 个一组翻转链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

---

1-思路

• 1. dummyHead：设置虚拟头结点，通过虚拟头结点保证每个结点的地位相同
• 2. 定位 pre 和 end 拆链：借助 pre 、start 和 end 指针：翻转 区间内的链表
  • 其中 pre 指针记录的是，被翻转部分的前一个结点
  • 其中 start 指针记录的是，被翻转链表的首节点
  • 其中 end 指针记录的是翻转链表的最后一个结点，end 一直移动
  • 2.1 定位 思路，利用循环定位 end
    • 2.1.1 while循环：利用 while 循环，只要 end.next != null
    • **2.1.2 判断是否满足k **：判断是否满足 k 个一组条件，令 i 从 1 开始遍历，遍历到 k ，同时 end != null 移动 end 。遇到 end 为 null 直接 break
  • 2.2 拆链
    • ① 先用 next 记录位置
    • ② 拆掉 end.next 断链
    • ③ 拆掉 pre.next
• 3. 翻转：翻转固定区间 start 和 end 内的链表
  • 3.1 翻转后用 pre.next 接收
  • 3.2 更新 pre 和 end 指针

---

2- 实现

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

class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 定义 pre 、endListNode dummyHead = new ListNode(-1);dummyHead.next = head;ListNode pre = dummyHead;ListNode end = dummyHead;while(end.next!=null){// k 个一组for(int i = 0 ; i < k && end!=null ;i++){end = end.next;}if(end == null){break;}// start ListNode start = pre.next;ListNode tmp = end.next;pre.next = null;end.next = null;pre.next = reverseList(start);// 更新 start  和 prestart.next = tmp;pre = start;end = start;}return dummyHead.next;}// 单链表翻转逻辑public ListNode reverseList(ListNode head){if(head==null || head.next == null){return head;}ListNode cur = reverseList(head.next);head.next.next = head;head.next = null;return cur;}
}

---

3- ACM实现

public class reverseList {// 链表static class ListNode{int val;ListNode next;ListNode(){}ListNode(int x){val = x;}}// k一组翻转public static ListNode reverseK(ListNode head,int k){// 定义dummyHeadListNode dummyHead = new ListNode();dummyHead.next = head;ListNode pre = dummyHead;ListNode end = dummyHead;// 定位 endwhile(end.next!=null){// k 个一组for(int i = 0 ; i < k && end!=null; i++){end = end.next;}//if(end==null){break;}// 断链ListNode start = pre.next;ListNode tmp = end.next;pre.next = null;end.next = null;// 翻转pre.next = reverseL(start);// 更新 start 、 pre 和 endstart.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);System.out.println("输入链表长度");int n  = sc.nextInt();System.out.println("输入链表");ListNode head=null,tail=null;for(int i = 0 ; i < n ; i++){ListNode newNode = new ListNode(sc.nextInt());if(head==null){head = newNode;tail = newNode;}else{tail.next = newNode;tail = newNode;}}System.out.println("输入要以几个一组反转链表");int k = sc.nextInt();// 翻转后的链表ListNode forRes = reverseK(head,k);while (forRes!=null){System.out.print(forRes.val+" ");forRes = forRes.next;}}
}

这篇关于【CT】LeetCode手撕—25. K 个一组翻转链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---