## 25. K 個一組翻轉鏈表 * 題目難度：困難 * 源碼地址：https://gitee.com/mgang/leet-code/blob/master/java/src/main/java/com/mango/leet/code/hard/LC25.java ~~~ package com.mango.leet.code.hard; /** * 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 * 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 */ public class LC25 { //Definition for singly-linked list. 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 prev = null; ListNode curr = head; int len = 0; // 后移動 while (curr != null){ len ++; curr = curr.next; } // 長度小于k時，直接返回原鏈表 if(len < k){ return head; } curr = head; // 遍歷 ListNode next = null; int n = k; while(curr != null && n-- > 0){ next = curr.next; curr.next = prev; prev = curr; curr = next; } // 遞歸翻轉 ListNode partPrev = reverseKGroup(curr,k); // 整合2部分鏈表 head = prev; while (prev.next != null){ prev = prev.next; } prev.next = partPrev; return head; } } } /** * 2022-03-02 * 思路： * 1. 判斷鏈表長度len,如果len<k則直接返回鏈表，不需要翻轉 * 2. 翻轉鏈表的k個元素，得到prev和curr 2個斷開的鏈表 * 3. 將curr指向的后續鏈表遞歸翻轉整合得到partPrev * 4. 將翻轉好的prev和partPrev2個鏈表整合后返回 */ ~~~