leetcode K个一组翻转链表

1、题目链接

25. K 个一组翻转链表 - 力扣（LeetCode）

2、题目描述

3、题目分析

a.每次根据输入的开始节点，得出k个节点之后的结束节点，即分组，然后返回该结束节点。注意有可能不够k个节点，就会返回null。

public ListNode getKGroupEnd(ListNode start,int k){
    while(--k!=0&&start!=null){
        start=start.next;
    }
    return start;
}

b.将分好组的start和end之间的节点翻转，需要提前记录下end的下一个节点（作为下一组的开始节点，循环往复），当前组翻转之后的尾节点需要抓住下一个开始节点。

public void reverse(ListNode start,ListNode end){
    ListNode nextStart=end.next;
    //新建一个cur变量，保证start的指向不变，后面需要用到start指向的节点。
    ListNode cur=start;
    ListNode pre=null;
    //翻转到下一个开始节点就结束
    while(cur!=nextStart){
        //单链表翻转的逻辑
        ListNode next=cur.next;
        cur.next=pre;
        pre=cur;
        cur=next;
    }
    //这句很关键，当前组的尾节点（翻转之后start变成了尾节点）
    //的next指针指向了下一句的开始节点，否则下一组的开始节点就找不到了
    start.next=nextStart;
}
    

c.最后在主函数里组合上述两个步骤，主函数要返回修改后的头节点，修改后的头节点一定是第一组翻转之后的结束节点，所以第一组要在循环外单独处理，为了返回处理之后的头节点。需要特别注意的是，b步骤之后上一组的结束节点指向了下一组的开始节点，但是等下一组翻转之后（开始节点就会变成结束节点，所以上一组的next指针的指向要更改）。

public ListNode reverseKGroup(ListNode head, int k) {
    if(head==null){
        return null;
    }
    ListNode start=head;
    ListNode end=getKGroupEnd(start,k);
    //说明第一组就不够k个节点
    if(end==null){
        //不够k个，不用翻转，返回当前头节点
        return head;
    }
    //够k个，则头节点为当前的end节点
    head=end;
    //翻转第一组
    reverse(start,end);
    //
    ListNode preEnd=start;
    while(preEnd.next!=null){
        //说明之后还有元素
        start=preEnd.next;
        end=getKGroupEnd(start,k);
        if(end==null){
        //不够k个，不用翻转，返回当前头节点
            return head;
        }
        reverse(start,end);
        preEnd.next=end;
        preEnd=start;
    }   
    return head;
}

4、运行结果