92. Reverse Linked List II - Medium

前往題目

想法

• 先找左右邊界，然後再根據左右邊界定位翻轉

思路

結果left和right根本就是index，還是1-based的

1. 找到left node
2. 循環right - left + 1次，期間都翻轉node
3. 最後再拼接

Code

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head.next == null) return head;

        ListNode dummy = new ListNode(-501, head);

        ListNode leftPrev = dummy, cur = head;
        
        // Find the left
        for (int i = 0; i < left - 1; ++i) {
            leftPrev = cur;
            cur = cur.next;
        }

        ListNode prev = null;
        // Start reversing
        for (int i = 0; i < right - left + 1; ++i) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        // Updating the pointers
        leftPrev.next.next = cur;
        leftPrev.next = prev;

        return dummy.next;
    }
}