##### Updated on February 10, 2019

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 thesublistin 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`

- With

## Approach

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`

.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.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
```