coderz.py

Problem

Write a function to reverse a Linked List in place. The function will take in the head of the list as input and return the new head of the list.

You are given the example Linked List Node class:

class Node(object):
    
    def __init__(self,value):
        
        self.value = value
        self.nextnode = None

Solution

Since we want to do this in place we want to make the functions operate in O(1) space, meaning we don’t want to create a new list, so we will simply use the current nodes! Time-wise, we can perform the reversal in O(n) time.

We can reverse the list by changing the next pointer of each node. Each node’s next pointer should point to the previous node.

In one pass from head to tail of our input list, we will point each node’s next pointer to the previous element.

Make sure to copy current.next_node into next_node before setting current.next_node to previous. Let’s see this solution coded out:

def reverse(head):
    
    # Set up current,previous, and next nodes
    current = head
    previous = None
    nextnode = None

    # until we have gone through to the end of the list
    while current:
        
        # Make sure to copy the current nodes next node to a variable next_node
        # Before overwriting as the previous node for reversal
        nextnode = current.nextnode

        # Reverse the pointer ot the next_node
        current.nextnode = previous

        # Go one forward in the list
        previous = current
        current = nextnode

    return previous

Test Your Solution¶

You should be able to easily test your own solution to make sure it works. Given the shortlist a,b,c,d with values 1,2,3,4. Check the effect of your reverse function and make sure the results match the logic here below:

# Create a list of 4 nodes
a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)

# Set up order a,b,c,d with values 1,2,3,4
a.nextnode = b
b.nextnode = c
c.nextnode = d

Now let’s check the values of the nodes coming after a, b and c:

print(a.nextnode.value)
print(b.nextnode.value)
print(c.nextnode.value)

2 3 4

d.nextnode.value

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-45-be675f4ae643> in <module>()
----> 1 d.nextnode.value

AttributeError: 'NoneType' object has no attribute 'value'

So far so good. Note how there is no value proceeding the last node, this makes sense! Now let’s reverse the linked list, we should see the opposite order of values!

reverse(a)

<__main__.Node at 0x104bd7dd0>

print(d.nextnode.value)
print(c.nextnode.value)
print(b.nextnode.value)

3 2 1

print(a.nextnode.value) # This will give an error since it now points to None

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-50-4057c9bc3c14> in <module>()
----> 1 print a.nextnode.value # This will give an error since it now points to None

AttributeError: 'NoneType' object has no attribute 'value'

Recommended: Understand The Singly Linked List and its Operation

Follow Me ❤😊

If you like my post please follow me to read my latest post on programming and technology.

Instagram

Facebook