Reverse Linked List II

Medium

Python

def reverse_between(head,left,right):
    dummy=type('N',(),{'val':0,'next':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

public ListNode reverseBetween(ListNode head,int left,int right){
    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 nxt=cur.next; cur.next=nxt.next;
        nxt.next=pre.next; pre.next=nxt;
    } return dummy.next;
}

Key Insight

In-place partial reversal. range vs loop.

Python → Java Differences

range(left-1) vs i<left-1
Reversal technique identical
Dummy head pattern

Python

def reverse_between(head,left,right):
    dummy=type('N',(),{'val':0,'next':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

public ListNode reverseBetween(ListNode head,int left,int right){
    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 nxt=cur.next; cur.next=nxt.next;
        nxt.next=pre.next; pre.next=nxt;
    } return dummy.next;
}

Algorithm Steps

1. Navigate to left
2. Reverse right-left times

← Previous All Linked Lists Next →