您现在的位置是：首页 >学无止境 >【Java力扣题库-K个一组翻转链表-内外循环】网站首页学无止境

假设链表为 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9，并且 k = 4。我们将对每 4 个节点进行反转。

初始状态

• 链表：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
• 虚拟头节点 dummy：0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
• 指针初始化：
  • before 指向虚拟头节点 0。
  • after 指向链表的第一个节点 1。

第一轮反转（处理节点 1, 2, 3, 4）

初始指针状态

• before: 指向 0
• after: 指向 1

执行代码逻辑

我们通过内层循环（j < k - 1，即 j < 3）逐步将节点插入到 before 和 before.next 之间。

第一次迭代（处理节点 2）

1. ListNode temp = after.next;
   • temp 指向 2。
2. after.next = temp.next;
   • 修改 after.next，跳过 temp，指向 3。
     链表变为：1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9。
3. temp.next = before.next;
   • 将 temp.next 指向 before.next，即 1。
     链表变为：2 -> 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9。
4. before.next = temp;
   • 更新 before.next 指向 temp，即 2。
     链表变为：0 -> 2 -> 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9。

第二次迭代（处理节点 3）

1. ListNode temp = after.next;
   • temp 指向 3。
2. after.next = temp.next;
   • 修改 after.next，跳过 temp，指向 4。
     链表变为：1 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9。
3. temp.next = before.next;
   • 将 temp.next 指向 before.next，即 2。
     链表变为：3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9。
4. before.next = temp;
   • 更新 before.next 指向 temp，即 3。
     链表变为：0 -> 3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9。

第三次迭代（处理节点 4）

1. ListNode temp = after.next;
   • temp 指向 4。
2. after.next = temp.next;
   • 修改 after.next，跳过 temp，指向 5。
     链表变为：1 -> 5 -> 6 -> 7 -> 8 -> 9。
3. temp.next = before.next;
   • 将 temp.next 指向 before.next，即 3。
     链表变为：4 -> 3 -> 2 -> 1 -> 5 -> 6 -> 7 -> 8 -> 9。
4. before.next = temp;
   • 更新 before.next 指向 temp，即 4。
     链表变为：0 -> 4 -> 3 -> 2 -> 1 -> 5 -> 6 -> 7 -> 8 -> 9。

更新指针

• before = after;
  • before 移动到 1。
• after = after.next;
  • after 移动到 5。

第二轮反转（处理节点 5, 6, 7, 8）

初始指针状态

• before: 指向 1
• after: 指向 5

重复上述步骤，最终链表变为：
0 -> 4 -> 3 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5 -> 9

第三轮（不足 k 个节点，不反转）

最后一组只有 9 一个节点，不足 k = 4，因此不做任何操作。

最终结果

链表变为：
4 -> 3 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5 -> 9

总结

通过上述步骤，我们成功地将链表按每 4 个节点为一组进行了反转。

代码如下：

package test30;

import java.util.ArrayList;

/**
 * Desc: K个一组翻转链表
 * Author: YYB
 * Date: 2025/2/12
 * 思路：
        定义一个辅助函数求整个链表长度，再除以k求整，求有几组，然后每组都进行翻转，那就要整两个循环，外层循环控制
        该对第几组进行操作，内层循环控制迭代的次数，

 */
public class test25 {
    //定义链表
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //定义辅助函数用于求整个链表长度
    private static int getLength(ListNode head){
        int length=0;
        while (head!=null){
            length++;
            head=head.next;
        }
        return length;
    }
    //定义主函数
    public static ListNode  reverseKGroup(ListNode head, int k){
        //先处理链表边界问题
        if (head==null||k==1){
            return head;
        }
        //定义虚拟头结点和两个指针before和after用于后续操作
        ListNode dummy = new ListNode(0);
        dummy.next=head;
        ListNode before=dummy;
        ListNode after=head;

        //计算需要对几组进行翻转，用于控制外循环
        int length=getLength(head);
        int times=length/k;

        //两层循环
        for (int i = 0; i < times; i++) {
            //例如对1234进行翻转，每次current指针分别指向234，只用迭代k-1次就行
            for (int j = 1; j < k; j++) {
                //定义current指针用于指向每次迭代要操控的节点，注：before和after在这第一组节点里始终指向0和1
                ListNode current=after.next; // current指向2
                after.next=current.next; // 链表变成：1 -> 3 -> 4 ，2被删了
                current.next=before.next; //链表变成：2 -> 1 -> 3 -> 4
                before.next=current; //链表变成：0 -> 2 -> 1 -> 3 -> 4，然后再迭代时，current指向并开始控制3
            }
            //链表变成0 -> 4 -> 3 -> 2 -> 1 -> 5 -> 6 -> 7 -> 8 -> 9后
            //开始处理第二组，则before要指向下一组的前一个节点，也就是1，after指向5
            before=after;
            after=after.next;
        }
        return dummy.next;
    }
    //测试用例
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, new ListNode(7, new ListNode(8, new ListNode(9)))))))));
        ListNode head=reverseKGroup(listNode,4);
        ArrayList<Integer> res = new ArrayList<>();
        while (head!=null){
            res.add(head.val);
            head=head.next;
        }
        System.out.println(res);
    }
}