reverse sublist

Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 m n length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Reversing a sublist in one pass is a notoriously hard problem. It requires meticulous and painstaking pointer work.

Solution

The first step is to create a dummy head, and a pointer P to the node before the head of the sublist.

Next, a tail pointer is created, pointing to the node after the head 'P'.

Do notice that the tail pointer doesn't move, rather it points to the next node after the sublist. Do also notice that P always points to the start of the sublist.

For this rewiring to take place, a tmp variable is used to iterate over the nodes that need changing.

The tmp variable acts as an iterator of sorts, it's the main point of interest during the iteration. During the iteration we:

• connect the tail to tmp's next.
• connect tmp to P's next.
• connect P's next to tmp.

The pattern is tail, tmp, p. This graphic will help you remember this pattern visually.

 1def reverse_sublist(L, start, finish):
 2    dummy = P = ListNode(0, L)
 3    for _ in range(1, start):
 4        P = P.next
 5
 6    tail = P.next
 7    for _ in range(finish - start):
 8        tmp = tail.next
 9        tail.next, tmp.next, P.next = (tmp.next, sub.next, tmp)
10    return dummy.next

Time and Space Complexity

$$time = O(n)$$ $$space = O(1)$$