Reverse Linked List II

Reverse only positions left to right, in one pass: stand just before the section and keep moving the node after curr to the front of it.

The idea

Walk prev to the node just before position left; it never moves again. curr is the first node of the section. Each round takes the node right after curr, unhooks it, and splices it in directly after prev, so it becomes the new front of the section. curr slides one place back every time, and after right - left rounds the section is fully reversed, all in one pass and O(1) memory.

Code

public ListNode ReverseBetween(ListNode head, int left, int right) {
    var dummy = new ListNode(0, head);
    ListNode prev = dummy;
    for (int i = 1; i < left; i++) prev = prev.next; // stop just before position left
    ListNode curr = prev.next; // first node of the section: it drifts to the back
    for (int i = 0; i < right - left; i++) {
        ListNode next = curr.next;
        curr.next = next.next;  // lift next out of its place
        next.next = prev.next;  // aim it at the current front of the section
        prev.next = next;       // and make it the new front
    }
    return dummy.next;
}

Tips

• The dummy node D makes left = 1 work with no special case: prev simply stays on D.
• Do the three assignments in this order. curr.next = next.next first saves the rest of the list before next.next is overwritten.
• curr is never reassigned inside the loop. It starts as the first node of the section and ends as its last.
• Try left = 1 and right = the length: the whole list is reversed.

In the .NET library

new ListNode(0, head) uses the two-argument constructor from the LeetCode ListNode class (val, next), so the dummy is linked in one expression.