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