92. Reverse Linked List ii #

题目 #

给定单链表头节点head和两个整数left和right，其中left <= right。反转从位置left到位置right的链表节点，返回反转后的链表。

思路 #

代码 #

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; }
}
class Solution {
    public void reverseList(ListNode head, ListNode tail) {
        if (head == tail) return;
        reverseList(head.next, tail);
        head.next.next = head;
    }
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode sentinel = new ListNode(-1, head);
        ListNode beforeLeft = sentinel, ptrRight = sentinel;
        for (int i=0; i<left-1; i++) beforeLeft = beforeLeft.next;
        for (int i=0; i<right; i++) ptrRight = ptrRight.next;
        ListNode ptrLeft = beforeLeft.next, afterRight = ptrRight.next;
        reverseList(ptrLeft, ptrRight);
        beforeLeft.next = ptrRight;
        ptrLeft.next = afterRight;
        return sentinel.next;
    }
}