题目链接

92. 反转链表 II

思路

和【链表】LeetCode 206. 反转链表的思路一样，只不过需要调整一下realHead头结点的位置，同时原题中的null在本题中为rightNode的下一个结点。

注意： 如果left == 1则说明head结点也需要被反转，此时反转后的首结点为rightNode需要在返回的时候单独判断。

代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {

        if(left == right){
            return head;
        }

        ListNode realHead = new ListNode(-1, head);
        for(int i = 1; i < left; i++){
            realHead = realHead.next;
        }

        ListNode rightNode = new ListNode(-1, head);
        for(int i = 0; i < right; i++){
            rightNode = rightNode.next;
        }
        ListNode endNode = rightNode.next;

        ListNode p = realHead.next;
        realHead.next = endNode;
        while(p != endNode){
            ListNode q = p.next;
            p.next = realHead.next;
            realHead.next = p;
            p = q;
        }

        return left == 1 ? rightNode : head;
    }
}