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

---

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

---

1- 思路

双指针 start 和 end + 链表翻转

实现思路：

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

---

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;}}
}