Reversing a sublist within a linked list

rev_sublist.cpp

/*
There are three sections of the list:
	1. The part before the sub list that gets reversed
	2. The actual sub list that gets reversed
	3. The part after the sub list that gets reversed
When reversing the entire list, (1) and (3) are empty, and (2) is the entire list.
	
 In the following code:
	• You need to traverse the list until you get to the p'th node and then only reverse 'q - p + 1' times (length of the window)
		○ When reversing the entire list, p = 0 and q = length of list - 1 so you don't need to do this.
	• The initial value of curr defines the first node to be processed i.e. node 2
		○ This value is worth saving before doing any reversals, because it becomes the last value in the reversed sublist i.e. node 2
		○ When reversing the entire list, it becomes the last node of the whole list
	• The final value of curr will point to the first node in the sublist that follows the reversed sublist
		○ In this case, curr would end up as node 5
		○ When reversing the entire list, curr overflows out of the list and becomes nullptr
	• The initial value of prev should be the last node that precedes the sublist to be reversed
		○ In this case, it should be node 1. 
		○ When reversing the entire list, it is nullptr, so you don't need extra processing to get this value. 
	• The final value of prev will hold the head of the reversed sublist
		○ In this case, it will be node 4
		○ When reversing the entire list, it becomes the head of the entire linked list instead

*/

ListNode *reverse(ListNode *head, int p, int q) {
    if (p == q) {
      return head;
    }

    // after skipping 'p-1' nodes, current will point to 'p'th node
    ListNode *current = head, *previous = nullptr;
    for (int i = 0; current != nullptr && i < p - 1; ++i) {
      previous = current;
      current = current->next;
    }

    // we are interested in three parts of the LinkedList, part before index 'p', part between 'p'
    // and 'q', and the part after index 'q'
    ListNode *lastNodeOfFirstPart = previous;  // points to the node at index 'p-1'

    // after reversing the LinkedList 'current' will become the last node of the sub-list
    ListNode *lastNodeOfSubList = current;
    ListNode *next = nullptr;  // will be used to temporarily store the next node

    // reverse nodes between 'p' and 'q'
    for (int i = 0; current != nullptr && i < q - p + 1; i++) {
      next = current->next;
      current->next = previous;
      previous = current;
      current = next;
    }

    // connect with the first part
    if (lastNodeOfFirstPart != nullptr) {
      lastNodeOfFirstPart->next = previous;  // 'previous' is now the first node of the sub-list
    } else {  // this means p == 1 i.e., we are changing the first node (head) of the LinkedList
      head = previous;
    }

    // connect with the last part
    lastNodeOfSubList->next = current;

    return head;
  }