leetcode 92. Reverse linked list II

Not the whole list in reverse order , Is to take a paragraph , stay left ~ right The linked list of this range is in reverse order .

Ideas ：

First, clarify how to reverse the order ,
Because it's a linked list , So numbers are not just exchange , It can be inserted in front .

Take the above example ,2->3->4 The reverse order of becomes 4->3->2

hold 2 The following numbers are inserted in turn to the front , That is, complete the reverse order ：
3->2->4, 4->3->2

Then how to judge which is the front , So you need a pre node , Point to left Previous node ,
Then if left yes head What about nodes ,
You need one newHead, newHead.next = head,
It's also convenient that we don't have to change back and forth head node .

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