92. Reverse Linked List II

same idea is used in algorithm 2 of reverse linked list

p: pre, c: cur, t: tail
1 -> 2 -> 3 -> 4 -> 5
p    t    c
1 -> 3 -> 2 -> 4 -> 5
p         t    c
1 -> 4 -> 3 -> 2 -> 5
p              t

1 find out pointer pre which points to node m - 1
2 insert nodes into position behind pre one by one

tip: link the end of the linked list to be reversed to the begin of the linked list which has not been processed, thus tail->next is the next node to be processed

ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummy(0);
        dummy.next = head; //able to handle m == 1
        
        ListNode* pre = &dummy; //point to m - 1
        n -= m;
        while (--m > 0 && pre->next) {
            pre = pre->next;
        }
        
        ListNode* tail = pre->next; //point to end pointer of the range
        while (n-- > 0) { //insert cur into the behind of pre
            ListNode* cur = tail->next;
            tail->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
        }
        return dummy.next;
    }

92. Reverse Linked List II - cocoder39/coco39_LC GitHub Wiki