25. K 个一组翻转链表（最详细注释，分成三个步骤进行处理，简单易懂）

布满荆棘的人生 2024-04-01 12:12 7阅读 0赞

算法描述：

> 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
> 
> k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
> 
> 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

![在这里插入图片描述][e3705900808546899388bc79d35375ac.png]

### 算法思路： ###

将这道题可以分解成几个部分  
![在这里插入图片描述][54efc875c3b34815a59b40ec4f201e3a.png]  
以中间情况进行举例

1.  先将自身4-3链表反转
2.  和上一个链表的结尾进行连接
3.  和下一个链表的开始进行连接

然后开始分别解决。

**完整代码可直接看文章结尾**

先写好循环

while(head!=null){
        
    	// 处理反转
    }

### 1. 将自身反转 ###

使用链表头插法进行自身反转，不同的是这里反转了k个节点就停止。  
首先找到这个子链表的开头和结尾，然后略微修改一下头插法即可。  
开头不用找，找一下结尾。  
定义一个方法getEnd专门用于查结尾。

#### 找结尾节点 ####

// 找到最后一个节点 return null 说明最后已经不够k个了
    private ListNode getEnd(ListNode head, int k){
        
            int index = 1;
            while(head != null){
        
                head = head.next;
                if(++index == k){
        
                    return head;
                }  
            }
            return head;
        }

这里有个细节，如果找的是最后一段子链表，且不足k个节点，那就保持原有顺序。所以调用该方法返回值为null即保持原有顺序。

// 获取最后一个节点，用于反转
          ListNode end = getEnd(head,k);
          // 如果到了最后不够了，保持原有顺序，直接返回即可
          if(end == null){
        
              break;
          }

也就是在此时就可以直接终结循环了。

#### 将自身子链表反转 ####

其实这里就很简单了，结尾节点已知，简单推理一下即可。  
定义一个方法reverseList专门用于反转子链表

// 反转head-end之间的链表
         private ListNode reverseList(ListNode head,ListNode end) {
        
            if(head == null || head.next == null){
        
                return head;
            }
           
            ListNode next = head.next;
            head.next=null;
    
            ListNode p;
           
            while(next != null && head != end ){
        
                p = next.next;
                next.next = head;
                head = next;
                next = p;
            } 
            return head; 
        }

在循环中直接调用即可

// 反转本身，head到end反转
           reverseList(head,end);

需要注意的时候，**在调用该方法后，传进来的head，返回的时候已经变成了该子链表的结尾。  
传进来的end，返回的时候已经变成了该子链表的开始。**

### 2. 与上一个链表进行连接 ###

那就在记录一下上一个链表的结尾 **last** 即可，也就是每次处理一个子链表后，将该子链表的结尾，赋给**last**，用于下一个链表处理。  
思考第一个链表的时候，其实last是没有的。那就创建一个保护节点protect，当作最先的last，同时该算法最后返回的时候，直接返回protect.next 即是最终的头节点。意外之喜！

#### 循环前定义last ####

// 定义一个保护节点
            ListNode protect = new ListNode(0,null);
            ListNode last = protect;

#### 每次处理子链表后，再赋值 ####

// 子链表的开头(现在的end)和上一个链表结尾结合
            last.next = end;

#### 下一次循环时，last就是该子链表的结尾 ####

// 当前结尾下一个循环时已成上一个链表的结尾（即目前的head）
          last = head;

### 3. 与下一个链表进行连接 ###

要记录下一个链表的开头**nextGroupStart**，但是在处理完子链表后，肯定已经找不到它了，所以在处理前就要先记录。

循环前，定义一下

ListNode nextGroupStart = null;

在循环内部，在处理子链表前赋值

// 记录后一个链表的开始
           nextGroupStart = end.next;

然后在处理完子链表后，再进行连接

// 子链表的结尾(现在的head)和下一个链表开始结合
           head.next = nextGroupStart;

让下一个子链表开始处理

// 让下一个子链表开始处理吧
           head = nextGroupStart;

最后，考虑到一些异常情况，比如空指针，k=1或者0的时候其实根本不用处理等等

if(k==1 || k== 0|| head == null || head.next == null){
        
             return head;
    }

最后的最后，直接上完整代码

/**
     * 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) {
        
            if(k==1 || k== 0|| head == null || head.next == null){
        
                return head;
            }
            // 定义一个保护节点
            ListNode protect = new ListNode(0,null);
            ListNode last = protect;
            ListNode nextGroupStart = null;
    
            // 反转一串链表， 前一个链表的结尾 + 反转本身 + 后一个链表的开始
            while(head!=null){
        
                // 获取最后一个节点，用于反转
                ListNode end = getEnd(head,k);
                // 如果到了最后不够了，保持原有顺序，直接返回即可
                if(end == null){
        
                    break;
                }
                // 记录后一个链表的开始
                nextGroupStart = end.next;
    
                // 反转本身，head到end反转
                reverseList(head,end);
                // 子链表的开头(现在的end)和上一个链表结尾结合
                last.next = end;
                // 子链表的结尾(现在的head)和下一个链表开始结合
                head.next = nextGroupStart;
    
                // 当前结尾下一个循环时已成上一个链表的结尾（现在的head）
                last = head;
                // 让下一个子链表开始处理吧
                head = nextGroupStart;
            }
            return protect.next;
    
    
        }
        // 找到最后一个节点 return null 说明最后已经不够k个了
        private ListNode getEnd(ListNode head, int k){
        
            int index = 1;
            while(head != null){
        
                head = head.next;
                if(++index == k){
        
                    return head;
                }  
            }
            return head;
        }
    
    
        // 反转head-end之间的链表
         private ListNode reverseList(ListNode head,ListNode end) {
        
            if(head == null || head.next == null){
        
                return head;
            }
           
            ListNode next = head.next;
            head.next=null;
    
            ListNode p;
           
            while(next != null && head != end ){
        
                p = next.next;
                next.next = head;
                head = next;
                next = p;
            } 
            return head; 
        }
    }

![在这里插入图片描述][62776008fcf5467abc4f45df3382a107.png]

[e3705900808546899388bc79d35375ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7c13a5a3280f462e8e38747e3081351e.png
[54efc875c3b34815a59b40ec4f201e3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/263831e106d447cfa80bcd38f40a4028.png
[62776008fcf5467abc4f45df3382a107.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ba97ef0ea40444f08ce33d71231a81b5.png