翻转链表

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //若left==right，则不需要翻转
        if(left==right) return head;
        //pre表示当前节点的前一个节点，用来连接第一段和第二段
        ListNode pre = new ListNode();
        pre.next = head;
        //作为结果返回
        ListNode res = pre;
        //表明pre是第count个节点的前一个节点
        int count = 1;
        //栈记录从left到right的节点
        Stack<ListNode> stack = new Stack<>();
        //先找到left节点所在的位置
        while(count<left){
            pre = pre.next;
            count++;
        }
        //将left到right的节点放入到栈中
        ListNode cur = pre.next;
        while(count<=right){
            stack.add(cur);
            cur = cur.next;
            count++;
        }
        //将第一段和第二段连接并将第二段的节点逆序
        while(!stack.isEmpty()){
            pre.next = stack.pop();
            pre = pre.next;
        }
        //连接第二段和第三段
        pre.next = cur;
        return res.next;
    }
}

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==right) return head;
        ListNode pre = new ListNode();
        pre.next = head;
        ListNode res = pre;
        int count = 1;
        //找到left节点的前一个节点的位置
        while(count<left){
            count++;
            pre = pre.next;
        }
        //cur表示已完成逆序的最后一个节点
        ListNode cur = pre.next;
        //first是left位置的节点，逆序后是left-right中的最后一个节点
        ListNode first = cur;
        //next表示未逆序的第一个节点
        ListNode next = cur.next;
        cur.next = null;
        //将left到right的节点逆序
        while(count<right){
            ListNode temp = next.next;
            next.next = cur;
            cur = next;
            next = temp;
            count++;
        }
        //连接第一段和第二段
        pre.next = cur;
        //连接第二段和第三段
        first.next = next;
        return res.next;
    }
}