package com.test;

import com.test.ListNode;

import java.util.Stack;

/**

 * Created by Demrystv.

 */

public class ReverseListNodeEveryK {

    /**

     * 使用栈的数据结构，时间复杂度是O(N)，空间复杂度是O(N)

     */

    public ListNode reverseListNodeEveryK(ListNode head, int k){

        if (k < 2){

            return null;

        }

        Stack<ListNode> stack = new Stack<ListNode>();

        ListNode newHead = head;

        ListNode cur = head;

        ListNode pre = null;

        ListNode next = null;

        while (cur != null){

            next = cur.next;

            stack.push(cur);

            if (stack.size() == k){

                pre = resign1(stack, pre, next);

                // 举例说明可得证，例如k = 3

                // 如果是1 2 ，那么不需要反转，程序也执行不到这个if里面来，所以返回的是 头节点

                // 如果是1 2 3 4 ，当执行到3的时候，到了这个if里面，这时满足newHead==head,所以newHead就是3，符合反转后  3 2 1 4

                // 如果是1 2 3 4 5 6 7，执行到3，newHead是3，执行到6，不满足newHead==head,所以newHead就是newHead,就是3，符合 3 2 1 6 5 4 7

                // 真是巧妙呀！！！

                newHead = newHead == head ? cur : newHead;

            }

            cur = next;

        }

        return newHead;

    }

    private ListNode resign1(Stack<ListNode> stack, ListNode left, ListNode right){

        ListNode cur = stack.pop();

        if (left != null){

            left.next = cur;

        }

        ListNode next = null;

        while (!stack.isEmpty()){

            next = stack.pop();

            cur.next = next;

            cur = next;

        }

        // 实际传入的这个right参数，是下一个K 范围内的第一个节点，不属于这个k 范围内。

        // 确保与后面的相连

        cur.next = right;

        // 实际返回的这个cur 是这个K范围内的最后一个节点，即下一个k 的上一个节点，即pre 的意思

        return cur;

    }

}