Problem #92: Reverse Linked List II

Intuition & Strategy Breakdown

Traverse to the node before position left. Reverse sublist between left and right in-place by adjusting node pointers, then reconnect with head.

Python Solution

def reverseBetween(head, left, right):
    if not head or left == right:
        return head
    
    dummy = ListNode(0, head)
    pre = dummy
    
    for _ in range(left - 1):
        pre = pre.next
        
    cur = pre.next
    for _ in range(right - left):
        nxt = cur.next
        cur.next = nxt.next
        nxt.next = pre.next
        pre.next = nxt
        
    return dummy.next

Java Solution

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || left == right) return head;
    
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;
    
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
    }
    
    ListNode cur = pre.next;
    for (int i = 0; i < right - left; i++) {
        ListNode nextNode = cur.next;
        cur.next = nextNode.next;
        nextNode.next = pre.next;
        pre.next = nextNode;
    }
    
    return dummy.next;
}