【算法题解】 8. K 个一组翻转链表

旧城等待， 2024-03-30 13:46 34阅读 0赞

#### 文章目录 ####

*   *  题目
     *  解题思路
     *  代码实现
     *  复杂度分析

### 题目 ###

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

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

**提示：**  
● 链表中的节点数目为 `n`  
● `1 <= k <= n <= 5000`  
● `0 <= Node.val <= 1000`

题目来自：[leetcode][]

### 解题思路 ###

**主体流程分以下三步：**

1.  将链表中的节点，从头开始每 `k` 个分为一组。
2.  将每组 `k` 个节点进行反转。
3.  将反转后的每个组链接起来。

**下面就主体流程中的每一步拆开来分析：**

1.  **分组：** 从起始点往后走 `k - 1` 步为一组，返回最后一个节点 `end`。不够 `k - 1` 步返回 `null`（不进行第第二步反转，直接和前面的组链接起来）。代码片段如下：

// 循环遍历链表中的每个节点
    while(head != null){
        
        // 获取分组中的最后一个节点
        ListNode end = getEnd(head, k);
        if(end == null){
        
            // 不够 k 个节点直接返回。
            break;
        }
    
        // 刚好取得 k 个节点，[head, end]。这里就可以准备进入第二步。
    
        // 下一组的开头 
        ListNode nextGroupHead = end.next;
        // head 指向下一组的开头，查找下一组。
        head = nextGroupHead;
               
    }

**2. 组内反转**：解法参考[【算法题解】7. 反转链表][7.]  
**3. 连接反转后的每一组**：每组反转后的节点 `end` 变为开头，`head` 变为结尾。要想链接每一组，需要将上一组的`head` 指向下一组反转后的开头（即下一组的`end`），这里需要考虑临界值，因为第一组没有上一组，所以我们可以开一个保护节点`pretect`。  
![K 个一组翻转链表][K]

### 代码实现 ###

/**
     * Definition for singly-linked list.
     * public 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 protectNode = new ListNode(0);
            ListNode lastGroupTail = protectNode;
    
            // 1. k个1组，进行分组
            while(head != null){
        
                ListNode end = getEnd(head, k);
                if(end == null){
        
                    // 不够 k 个元素直接返回, 跳出循环，无需反转。
                    break;
                }
    
                // 下一组的开头 
                ListNode nextGroupHead = end.next;
    
                // 2. 每组进行内部反转链表
                // [head, end] 为一组, 进行反转。
                this.reverse(head, end);
    
             
                // 3. 将反转后的列表连起来
                lastGroupTail.next = end;
                
                head.next = nextGroupHead;
    
                lastGroupTail = head;
                // head 指向下一组的开头，查找下一组。
                head = nextGroupHead;
               
            }      
    
            return protectNode.next; 
    
        }
    
        private ListNode reverse(ListNode head, ListNode end){
        
            ListNode pre = null;
            ListNode stop = end.next;
            // 这不能使用 wile(head != end.next), 因为循环内部会将end.next反转。
            while(head != stop){
        
                ListNode nextNode = head.next;
                head.next = pre;
                pre = head;
                head = nextNode;
            }
            return pre;
        }
    
        /**
        * 根据 head 向后找第 k - 1 个元素为 end, 如果不够 k 个元素直接返回null, 不用反转。
        */
        private ListNode getEnd(ListNode head, int k){
        
            while(head != null){
        
                k--;
                if(k == 0){
        
                    return head;
                }
                head = head.next;
            }
            return null;
        }
    
    
    }

### 复杂度分析 ###

**时间复杂度**  O ( n ) O(n) O(n)：`getEnd` 每次循环`k`次，最后一次 `<= k`，但是总体加起来是 `n`。`reverse` 每次的时间复杂度也是 `k`，加以来 `<= n`，因为最后一组可能需要反转。总的时间复杂度约为 `2n`, 忽略常数后为  O ( n ) O(n) O(n)；  
**空间复杂度**  O ( 1 ) O(1) O(1)：额外开启的变量都是常数级的，所以空间复杂度为 O ( 1 ) O(1) O(1)。

[leetcode]: https://leetcode.cn/submissions/detail/392176109/
[7.]: https://blog.csdn.net/justyuze/article/details/128512102
[K]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7ed66bbf53c14dfeb21ba98ccab1f3fa.gif