Leetcode 25. K 个一组翻转链表

╰+哭是因爲堅強的太久メ 2022-10-19 12:41 140阅读 0赞

#### 题目重述 ####

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

#### 进阶： ####

你可以设计一个只使用常数额外空间的算法来解决此问题吗？  
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

#### 示例 1： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]

输入：head = \[1,2,3,4,5\], k = 2  
输出：\[2,1,4,3,5\]

#### 示例 2： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70 1]

输入：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  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路分析 ####

*  预先实现链表-反转链表的前k个元素
 *  base case 是如果说不够k个就不反转
 *  把整体问题可以分解为：k个一组反转，就相当于先反转前k个元素，之后反转第二组就看成反转剩下部分链表的前k个元素。

#### Java实现 ####

class Solution {
        
        public ListNode reverseKGroup(ListNode head, int k) {
        
            // 判空
            if(head == null)
            {
        
                return null;
            }
            // 根据题意，若不够k个，则保持顺序不变
            // p用于判断是否满足k个，q用于后续链接结点
            ListNode p = head,q = head;
            for (int i = 0; i < k; i++) {
        
                // 不⾜ k 个，不需要反转，base case
                if (p == null) return head;
                p = p.next;
            }
            // 反转前k个结点，此时head不再是结果的头节点，r是
            ListNode r = reverseFrontN(head,k);
            // 对于剩下的链表，递归调用，继续k个一组反转链表
            // 前面反转前k个结点后，q就在前部分的末尾，链接即可。
            q.next = reverseKGroup(p,k);
            return r;
        }
        ListNode backNode = null;
        /**
         * 反转前 N 个结点
         * @param head
         * @param n
         * @return
         */
        public ListNode reverseFrontN(ListNode head,int n)
        {
        
            // 代表不用反转，但需要记录后驱结点,一般情况下记录一次即可
            if(n == 1)
            {
        
                backNode = head.next;
                return head;
            }
            // 以 head.next 为起点的部分链表，记作T，那么需要T的反转前 n - 1 个节点
            ListNode r = reverseFrontN(head.next,n-1);
            // 将链表T的末尾指向T前的那一个结点
            head.next.next = head;
            // 链接后驱结点
            head.next = backNode;
            return r;
        }
    }

#### 补充反转前N个结点链表 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]: /images/20221005/f2d7148768854744a21f94807cbebf99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70 1]: /images/20221005/b1d8bb1008bf43c1a31fbc6fbafc0484.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70 2]: /images/20221005/6959df9df7dc46ab9b3fc11784c03c7e.png