K个一组翻转

/**
 * 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; }
 * }
 */

思路1

1. 根据k分组
2. 该组翻转后
3. 拼接到原来的链表

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prevGroupEnd = dummy;
        while (true) {
            ListNode groupStart = prevGroupEnd.next;
            ListNode groupEnd = getGroupEnd(groupStart, k);
            if (groupEnd == null) {
                break;
            }
            ListNode nextGroupStart = groupEnd.next;
            groupEnd.next = null;
            prevGroupEnd.next = reverseLinkedList(groupStart);
            groupStart.next = nextGroupStart;
            prevGroupEnd = groupStart;
        }
        return dummy.next;
    }
    
    private ListNode getGroupEnd(ListNode start, int k) {
        for (int i = 1; i < k; i++) {
            if (start == null) {
                return null;
            }
            start = start.next;
        }
        return start;
    }
    
    private ListNode reverseLinkedList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }

思路2

根据之前2节点翻转的思路进行递归 翻转

1. 确认是否进行翻转
2. 找到头节点和尾节点
3. 翻转指定范围链表
4. 头节点.next 连接下一个翻转过的节点 // 这里使用递增
5. 返回新的头节点（原本尾节点）

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) return head;
        return reverse(head, k);
    }

    /**
     递归反转
     */
    ListNode reverse(ListNode node, int k) {
        int count = k;
        // 检查是否需要反转
        boolean check = check(node, count);
        if (!check) return node;
        // 处理指定范围节点

        // 找到最后一个节点
        ListNode lastNode = findLast(node, k);
        // get lastnode.next
        ListNode after = lastNode.next;
        // 倒排序
        ListNode newHead = requeue(node, k);
        // 首尾节点
        node.next = reverse(after, k);

        return newHead;

    }

    /**
     找到最后一个节点
     @主要耗时
     */
    ListNode findLast(ListNode node, int k) {
        ListNode tmp = node;
        k = k - 1;
        do {
            tmp = tmp.next;
            k--;
        } while (k > 0);
        return tmp;
    }

    /**
     指定部分倒序排列
     @主要耗时
     */
    ListNode requeue(ListNode node,int k) {
        Stack<ListNode> stack = new Stack<>();
        ListNode dual = node;

        // 节点入栈
        for (int i = 1; i <= k ;i ++) {
            stack.push(dual);
            dual = dual.next;
        }

        ListNode head = stack.pop();
        dual = head;
        // 出栈
        while(!stack.isEmpty()) {
            dual.next = stack.pop();
            dual = dual.next;
        }
        return head;

    }

    // 检查剩下的节点是否需要反转
    boolean check(ListNode node, int k) {
        ListNode tmp = node;
        while(k > 0) {
            if (tmp == null) return false;
            tmp = tmp.next;
            k --;
        }
        return true;
    }

Q.E.D.