Reversing a linked list: cutaway

A linked list is a sequential data structure. A head pointer points to the first node and each node has a pointer to the next. The last node is suitably terminated. Manipulating a linked list is an exact exercise and reversing it certainly so. Would a cutaway view be helpful?

A singly linked list traverses in only one direction unlike an array which can be traversed in both the forward as well as the reverse direction quite easily.

The recurrence relation

Reversing a linked list can be done two ways: iteratively and recursively. The recursive approach has a certain elegance to it and the algorithm is easier to construct given the recurrence relation:

Given a linked list L

$$ reverse(L) = head(L)\ appended\ to\ reverse(head.next) $$

$$ reverse(L) = head(L)\ if\ head(L)\ is\ the\ last\ node $$

where \(head.next\) is the part of the list following the head node.

Implementation Notes

The Node class

We start with implementation of the Node class. The two necessary attributes are val and nxt for the value of the node and the next pointer respectively. The __str__ method is implemented so as to print the entire linked list right up to the terminal node reachable from the current node making for a handy visualization. A tail() method returns a pointer to the terminal node. This method is helpful to us while appending a node to the linked list in the reversing process.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Node():
    '''
    A class that implements a linked list node.
    Node(val = None, nxt = None) returns Node
    '''
    def __init__(self, val = None, nxt = None):
        # Input: value for the node. Default: None
        self.val = val
        self.nxt = nxt
    
    def tail(self):
        # Return last node reachable from here
        cur = self   # get a pointer to this node
        while(cur.nxt != None):
            cur = cur.nxt
        return cur # Return terminal node
            
    def __str__(self):
        # print current node upto last reachable node for user
        return f"{self.val}->{self.nxt}"
        
    def __repr__(self):
        # print current node for debugging
        class_name = type(self).__name__
        if self.nxt != None:
            nxt_id = f"{id(self.nxt):x}"
        else:
            nxt_id = 'None'
        return f"{class_name}(val={self.val}) at {id(self):0x} linked to {nxt_id}"

Reversing the linked list: The revll() function

The reversal is performed by writing a separate function which is written outside the scope of the Node class. Our function implements the recurrence relations stated above. It has an optional flag to enable the cutaway mode. Reversal starts from the tail node reversing the direction of each link to point to the previous node.
This will become clearer in the cutaway view.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def revll(head,cutaway=False):
    # Reverse linked list
    # Input: head of linked list to be reversed
    # Returns: head of reversed linked list
    '''
    Statement of recurrence: given head, append head to reverse of rest of list.
    '''
    _cutaway = cutaway
    
    if head.nxt == None:   # At last node
        if cutaway:
            print("Cutaway view --------")
            print(f"[{head}], at terminal node of original list")
        return head

    else:
        last = head       # This node will become the tail of the reverse list
        rol = head.nxt    # Separate head and rest of list
        # Append last to reverse of rol or make it next node to tail of rol
        rhead = revll(rol, cutaway = _cutaway)
        last.nxt = None
        if cutaway: 
            print(f"Append [{last}] to part of reversed list [{rhead}]")
        rhead.tail().nxt = last
        return rhead

Let us now look at the driver code that constructs a linked list and reverses it in the cutaway mode.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

if __name__ == "__main__":
    '''Test the node class by creating a linked list.'''
    head = cur = None   # Initialize head and current pointer
    
    for i in range(10):   # Create a linked list of a series
        if head == None:  # First element
            head = Node(val = i)
            cur = head    # The current node is head node
        else:
            cur.nxt = Node(val = i)
            cur = cur.nxt
    # Print entire list for user.
    print(f"Original linked list:\n{head}")
    print(f"Reversed linked list:\n{revll(head,cutaway = True)}")

Running this gives us the following output:

Original linked list:
0->1->2->3->4->5->6->7->8->9->None
Cutaway view --------
[9->None], at terminal node of original list
Append [8->None] to part of reversed list [9->None]
Append [7->None] to part of reversed list [9->8->None]
Append [6->None] to part of reversed list [9->8->7->None]
Append [5->None] to part of reversed list [9->8->7->6->None]
Append [4->None] to part of reversed list [9->8->7->6->5->None]
Append [3->None] to part of reversed list [9->8->7->6->5->4->None]
Append [2->None] to part of reversed list [9->8->7->6->5->4->3->None]
Append [1->None] to part of reversed list [9->8->7->6->5->4->3->2->None]
Append [0->None] to part of reversed list [9->8->7->6->5->4->3->2->1->None]
Reversed linked list:
9->8->7->6->5->4->3->2->1->0->None

Understanding the cutaway

The linked list starts reversing from the tail node, which will be our head node at the end of the reversal. The function descends to the last node because of successive calls to reverse the ‘rest of the list’. Having reached the last node, it returns the last node itself as the head of the reversed list. Thereafter, the function returns in each called function and appends the corresponding ‘caller’ node to this reversed list. This process continues until the original head node – the first ‘caller’ node – is reached, thus reversing the entire linked list.