leetcode 25 Solution

代码解析

package com.demo.s25;

import java.util.ArrayList;
import java.util.List;

/**
 * K 个一组翻转链表
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/reverse-nodes-in-k-group
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    // 定一个数据结构，存放链表 分组
    class Pharse {
        //链表开始节点
        ListNode begin;
        //链表开始节点
        ListNode end;
        //链表是否需要翻转
        boolean reverse;

        public Pharse(ListNode begin, ListNode end, boolean reverse) {
            this.begin = begin;
            this.end = end;
            this.reverse = reverse;
        }

        public void reverseSubGroup() {
            //前置节点都未null
            ListNode pre = null;
            //当前节点为begin
            ListNode cur = begin;
            //开始翻转
            while(true) {
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                //需要判断翻转结束条件
                if(cur == end || tmp == null){
                    break;
                } else {
                    cur = tmp;
                }
            }
            //转向后给出新的交换后的 begin end
            ListNode tmp = begin;
            begin = end;
            end = tmp;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        //判断入参
        if(k == 1) {
            //一个元素直接返回
            return head;
        }
        //哑巴节点，标记头结点
        ListNode pre = new ListNode(0);
        //当前节点从head开始
        ListNode cur = head;
        //开始位置
        boolean flag = false;
        //链表分组
        List<Pharse> pharses = new ArrayList<>();
        //链表开始
        ListNode start = null;
        //链表结束
        ListNode end = null;
        //开始分组
        for(int i = 0; cur != null; i++) {
            //k个元素 开始的位置
            if(i % k == 0 && !flag) {
                start = cur;
                flag = true;
                //区间就一个元素了，开始即是结束
                if(cur.next == null) {
                    end = cur;
                    pharses.add(new Pharse(start, end, false));
                }
                //k个元素后 结束的位置
            } else if((i + 1) % k == 0 && flag) {
                end = cur;
                flag = false;
                pharses.add(new Pharse(start, end, true));
                //区间没有满k个元素，提前结束
            } else if(cur.next == null) {
                end = cur;
                pharses.add(new Pharse(start, end, false));
            }
            //下一个元素
            cur = cur.next;
        }
        ListNode ph = pre;
        for(Pharse pharse : pharses) {
            if(pharse.reverse) {
                //每个区间内翻转
                pharse.reverseSubGroup();
            }
            //多个区间指针反向修改
            ph.next = pharse.begin;
            ph = pharse.end;
        }

        return pre.next;

    }
}