How to Reverse a Circular Linked List in Python

Question

I have a circular linked list object that I'm practicing with and I'm stuck on the part where I have to reverse a circular linked list. I can find a lot of examples using Java & C, but no python examples. I tried to convert the logic from the C and Java programs but it's not coming out correctly. It only collects a portion of the list and seems to terminate early.

Here is the code I have so far where I define both my Node and CircularList object:

class Node(object):

    def __init__(self, data = None, next_node = None):
        self.data = data
        self.next_node = next_node


class CircularLinkedList(object):

    def __init__(self, head = None, end = None):
        self.head = head
        self.end = end

    def traverse(self):

        curr_node = self.head

        while curr_node.next_node:            
            print(curr_node.data)            
            curr_node = curr_node.next_node

            if curr_node == self.head:
                break


    def insert_end(self, data):

        new_node = Node(data) 

        # handle empty list case
        if self.head == None:            
            self.head = new_node
            self.head.next_node = new_node
            self.end = new_node
            return

        # handle non-empty list case
        if self.end != None:
            self.end.next_node = new_node
            new_node.next_node = self.head        
            self.end = new_node
            return


    def insert_beg(self, data):

        new_node = Node(data)
        new_node.next_node = self.head        
        curr_node = self.head

        # handle empty list case
        if curr_node == None:            
            self.head = new_node
            self.end = new_node
            self.head.next_node = new_node
            return

        # handle non-empty list case
        if self.end != None:
            self.end.next_node = new_node
            new_node.next_node = self.head        
            self.head = new_node
            return

    def insert_mid(self, ref_node, data):

        # handle empty node case
        if ref_node == None:
            print("You've selected an empty node.")

        # if we are inserting after the end node, then just use the insert_end method
        if ref_node == self.end:
            self.insert_end(data)
            return

        # otherwise it's a true mid.
        new_node = Node(data)            
        ref_next = ref_node.next_node        
        ref_node.next_node = new_node
        new_node.next_node = ref_next


    def delete_beg(self):

        if self.head != None:            
            aft_head = self.head.next_node
            self.end.next_node = aft_head
            self.head = aft_head
        else:
            print('The list is empty, no values to delete.')

    def delete_end(self):

        if self.end != None:

            curr_node = self.head

            while curr_node.next_node.next_node != self.head:                        
                curr_node = curr_node.next_node


            self.end = curr_node
            curr_node.next_node = self.head

    def delete_mid(self, position):

        if position == 0:            
            self.delete_beg()
            return

        if position == self.list_size():
            self.delete_end()
            return


        curr_node = self.head.next_node
        count = 0

        while count <= position:            
            count = count + 1 
            curr_node = curr_node.next_node

        curr_node.next_node = curr_node.next_node.next_node


    def list_size(self):

        curr_node = self.head

        count = 0

        while curr_node.next_node:            
            count = count + 1            
            curr_node = curr_node.next_node            
            if curr_node == self.head:
                break

        return count

I've tried different operations on the list and they all seem to work fine, but 'the part I'm now stuck on is this portion:

def reverse(self):

    if self.head == None:
        return

    last = self.head
    prev = self.head
    curr = self.head.next_node

    while self.head != last:

        self.head = self.head.next_node
        curr.next_node = prev
        prev = curr
        curr = self.head

    curr.next_node = prev
    self.head = prev

Here is the main section of my code where insert and delete values, and then try reversing the list:

# define a new list
circular_list = CircularLinkedList()

# insert a few values at the end
circular_list.insert_end(50)
circular_list.insert_end(60)
circular_list.insert_end(70)

# insert a few values at the beginning
circular_list.insert_beg(90)
circular_list.insert_beg(100)

# grab a node
first_node = circular_list.end

# insert value inbetween two nodes.
circular_list.insert_mid(first_node,20)

# delete the first and last value
circular_list.delete_beg()
circular_list.delete_end()

print('Before Reversal')
print('-'*20)
circular_list.traverse()

circular_list.reverse()

print('After Reversal')
print('-'*20)
circular_list.traverse()

But when I try to reverse it this is the output:

Before Reversal
--------------------
90
50
60
70
After Reversal
--------------------
90
50

The condition in the while loop in reverse can never be met, since you just initialized last to be equal to self.head. That means the loop body never runs, and so you're only fiddling with a few nodes, not the whole list. Is last supposed to be initialized to self.end perhaps, instead? — Blckknght
– Blckknght, Commented Aug 7, 2019 at 16:53
So if I change last to self.end I get an infinite loop that never terminates. That doesn't make sense to me because if I am reassigning self.head in the while loop, it should eventually equal the last node. — areed1192
– areed1192, Commented Aug 7, 2019 at 17:04
As @Bickknght already noted, all this does is to link the second node back to the first. I'm unclear on your algorithm -- you iterate head around the circle, while 'last` doesn't change (last element of the iteration?). — Prune
– Prune, Commented Aug 7, 2019 at 17:06

mashtock · Accepted Answer · 2019-08-07 17:11:38Z

1

By looking at your code, the reverse() function surely have a bug. You can easily see that you never start your while loop iteration because the condition is false at the beginning. I would do something like that:

def reverse(self):

    if self.head == None:
        return

    last = self.head
    curr = self.head
    prev = self.end
    next=curr.next_node
    curr.next_node = prev
    prev = curr
    curr = next
    while curr != last:
        next=curr.next_node
        curr.next_node = prev
        prev = curr
        curr = next

answered Aug 7, 2019 at 17:11

mashtock

4001 gold badge6 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

areed1192 Over a year ago

Your code worked perfectly, the only thing I added was curr.next_node = prev and self.head = prev at the end so it reassigned the head node.

Collectives™ on Stack Overflow

How to Reverse a Circular Linked List in Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related