public class 反转链表_92_法2_非递归_for{


//方法二：逻辑性强，没有用什么骚技巧，容易理解
    /*思路：（注意：在开始写代码之前要先把思路先在纸上理顺，不然逻辑很容易写混乱！思路理顺了代码就很容易写了）
    （1）先找出这个需要反转的区间，然后切断这个区间，使之成为独立的一个段。
    （2）反转这个区间（使用for循环即可）
    （3）然后让pre指向这个区间的末尾节点，让leftNode指向这个区间的首节点（实现反转后的链接）
    （4）return 头节点（dummy节点）

    */
    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 ListNode reverseBetween(ListNode head, int left, int right) {
        //注意：因为头节点可能发生变化，所以使用虚拟头节点，可以避免复杂的分类讨论
        ListNode dummyNode = new ListNode(-1);
        //dummyNode为head节点的前一个节点
        dummyNode.next=head;

        //for循环，找到left节点
        //子区间最左节点的前一个节点
        ListNode pre=dummyNode;
        for(int i=0;i<left-1;i++){
            pre=pre.next;
        }
        //走完for，现在的pre是指向left的前一个节点

        //子区间的最左节点
        ListNode leftNode=pre.next;

        //子区间的最右节点
        ListNode rightNode=leftNode;

        while(left!=right){
            rightNode=rightNode.next;
            left++;
        }
        //子区间最后一个节点的下一个节点
        ListNode after=rightNode.next;


        //（1）切断这个区间（边界处切割）
        pre.next=null;
        rightNode.next=null;

        //（2）反转这个区间链表
        reverseAll(leftNode);

        //(3)反转后，把整条链表链接起来
        //假设pre=1，leftNode=2，rightNode=4，after=5
        // 1->2->3->4->5
        //此时就得pre.next指向right；将leftNode.next指向after
        // 1-> 4->3->2 ->5
        pre.next=rightNode;
        leftNode.next=after;
        //返回头节点（注意不能return head，因为可能head节点有变化，这也是为什么用dummy节点的原因）
        return dummyNode.next;
    }


    //补充：这个函数有没有返回值无所谓
    public ListNode reverseAll(ListNode head){
        ListNode precur=null;
        ListNode cur=head;
        //因为是切断的一个区间，所以遍历到null即可
        while(cur!=null){
            //当前元素的下一个元素
            ListNode next=cur.next;
            //让当前节点的下一个节点向前指向（第一个cur节点指向的precur是null）
            cur.next=precur;
            //向后移动一位
            precur=cur;
            //向后移动一位
            cur=next;
        }
        //到这，已经完成了整个区间的逆转
        return head;
    }
}