Reversing sublists of singly linked lists

Singly linked lists can be tricky in its own right. Without the convenience of having a pointer to the previous node that is provided in doubly-linked lists, it can be really easy to be wasteful in performance with singly linked lists.

Problem

Given an index for the start and end of a sublist, reverse the sublist in a linked list.

Input

• head : Pointer to the entrance of the linked list
• s : Starting index of the sublist. The index starts at 1, where 1 represents the HEAD.
• 'f': Final index of the sublist. For example, if a link list of 3 nodes is defined such that: A -> B -> C, then f=3 represents the node that has the data C.

Examples:

• A -> B -> C -> D -> E
  • With s = 1, f = 3, the output would be: C -> B -> A -> D -> E
  • With s = 2, f = 5, the output would be: A -> E -> D -> C -> B

Approach

1. We only care about reversing from index s to index f, so we should keep iterating from the HEAD until we reach the node at index s.

2. Right before we begin the reversing of the specified sublist, we want to have a pointer to the node that points to the reversed sublist.

3. We store s_head.next into the temp variable, because we want s_head to point to a node further and further to the end of the sublist.

   For example, with a singly linked list such as W -> X -> Y -> Z, if we want to reverse X -> Y -> Z, then W should somehow point to Z so that the final output would be: W -> Z -> Y -> X.

   This means s_head.next will have to be re-assigned to a different node, so the old value will be lost unless we preserve it.

   Why do we need the old value? We still need a reference to the old s_head.next or temp because that node will need to point to the current node we are working on. Recall that originally, temp is pointing to the next node after the current node (that is, if A is the current node, and B is the node right after, then A -> B). Since we are trying to reverse the pointers, instead of A -> B, we want to do B -> A. By setting the next pointer of temp to prev.next, we are doing B -> A.

   Lastly, since we want to continue this reversing process multiple times, prev.next should be updated to temp because temp will be set to a new node (to the right of where it is currently set to) in the upcoming loops. This way, when we begin the next iteration, prev will correctly point to where temp used to be, especially because temp will be re-assigned as early as the first line in the loop (temp = s_head.next).

Solution

from linked_list import LinkedList

def reverse_sublist(head, s, f):  
    # O(f) time complexity, O(1) space complexity
    dummy = s_head = LinkedList(0, head)

    for _ in range(s-1): # See 1.
        s_head = s_head.next

    prev = s_head # See 2.
    s_head = s_head.next

    for _ in range(f-s): # See 3.
        temp = s_head.next
        s_head.next = temp.next
        temp.next = prev.next
        prev.next = temp

    return dummy.next