LeetCode: Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

---

There are 3 steps to solve this problem.

1. Find the node at position m and record the position ahead of m.

2. Start reversing nodes from m to n.

3. Concatenate node that recorded to the end of the reversal list and m node to n node's next.

C++ Code:

/*
 * func: reverse_between
 * goal: reverse nodes between m and n in the list
 * @param head: head node of the list
 * @param m: the starting index of reverse
 * @param n: the end index of reverse
 * return: new head of the linked list
 */
ListNode *reverse_between(ListNode *head, int m, int n){
    //Argument validation
    ListNode *iter = head;
    int count = 0;
    while(iter != nullptr){
        ++count;
        iter = iter->next;
    }
    if(!(m <= n && n <= count && m >= 1)){
        return head;
    }
    
    //Add one node to the current head to make it easiser
    ListNode *tmp_head = new ListNode(0);
    tmp_head->next = head;
    
    ListNode *prev = tmp_head;
    ListNode *curr = head;
    //Make curr move to the start point of the reverse part
    count = 1;
    while(count < m){
        prev = curr;
        curr = curr->next;
        ++count;
    }
    
    //Record the nodes where reverse will happen
    ListNode *starting = prev;
    ListNode *ending = curr;
    ListNode *next = nullptr;
    
    //Start reversing
    prev = curr;
    curr = curr->next;
    
    while(count < n){
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
        ++count;
    }
    //Concatenate the new head of the reversed part and end of the reversed part
    starting->next = prev;
    ending->next = curr;
    
    head = tmp_head->next;
    delete tmp_head;
    
    return head;
}

Python Code:

# func: reverse a linked list from position m to n
# @param head: head node of the list
# @param m: starting position m
# @param n: ending position n
# @return: new head node
def reverse_between(head, m, n):
    tmp_head = ListNode(0)
    tmp_head.next = head
    #Find position m
    prev = tmp_head
    count = 1
    while count < m:
        prev = prev.next
        count += 1
    start = prev
    end = prev.next

    #Start reversing
    prev = prev.next
    curr = prev.next
    while count < n:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
        count += 1

    start.next = prev
    end.next = curr

    return tmp_head.next