[数据结构与算法] 25. K 个一组翻转链表

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 25. K 个一组翻转链表 -> 正文阅读

[数据结构与算法]25. K 个一组翻转链表

在这里插入图片描述

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        //定义dummynode 初始化head\tail和pre
        ListNode dummynode=new ListNode(0);
        dummynode.next=head;
        ListNode pre=dummynode;
        ListNode tail=pre;
        while(head!=null){
            //找到tail的位置
            for(int i=0;i<k;i++){
                tail=tail.next;
                if(tail==null){
                    return dummynode.next;
                }
            }
            //重新连接——记录要翻转的链表的前后的两个节点  以及 翻转的链表的两头 
            ListNode reversenext=tail.next;
            ListNode[] reverse=subreverse(head,tail);
            head=reverse[0];
            tail=reverse[1];
            pre.next=head;
            tail.next=reversenext;
            //更新 pre和head，tail会根据head在之后的循环里面更新，reversenext会根据tail来更新
            pre=tail;
            head=tail.next;
        }
        return dummynode.next;
    }

    //传入头尾，翻转该链表,最后要得到这个的头尾
    ListNode[] subreverse(ListNode head,ListNode tail){
        ListNode pre =null;
        ListNode cur=head;
        tail.next=null;
        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=pre;

            pre=cur;
            cur=temp;
        }
        return new ListNode[]{tail,head};//头尾节点标志没变，可以直接返回
    }
}