reverse a LinkedList
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155
class Node():
def __init__(self, value, next_node=None):
self.value = value
self.next_node = next_node
class LinkedList():
def __init__(self, value_first_item):
self.head = Node(value_first_item)
self.length = 1
self.tail = self.head
def get_head(self):
return self.head.value
def get_tail(self):
return self.tail.value
def append(self, value):
new_node = Node(value)
self.tail.next_node = new_node
self.tail = new_node
self.length+=1
def prepend(self, value):
new_node = Node(value, self.head)
self.head = new_node
self.length+=1
def get_position(self, position):
""" get the value of a specific position in the linked list."""
if position < 0:
raise IndexError("No negative positions")
elif position > self.length-1:
return None
raise IndexError("Position out of boundaries")
elif position == self.length-1:
return self.get_tail()
elif position == 0:
return self.get_head()
curr_node = self.head
curr_position = 0
while curr_node.next_node != None:
if curr_position == position:
return curr_node.value
else:
curr_node = curr_node.next_node
curr_position+=1
def insert(self, value, position):
""" Insert a new node in the middle of the list"""
if position < 0:
raise IndexError("No negative positions")
elif position > self.length-1:
raise IndexError("Position out of boundaries")
curr_node = self.head
curr_position = 0
while curr_node.next_node != None:
if curr_position == position-1:
new_node = Node(value, curr_node.next_node)
curr_node.next_node = new_node
self.length+=1
break
else:
curr_node = curr_node.next_node
curr_position += 1
def printLinkedList(self):
curr_node = self.head
curr_position = 0
print(f"{curr_position}: {curr_node.value}")
while curr_node.next_node != None:
curr_node = curr_node.next_node
curr_position+=1
print(f"{curr_position}: {curr_node.value}")
def reverse(self):
"""
- Reversed = None
- toReverse = head
- nextToReverse = head.next
- toReverse.next = Reversed.addr or None
-
- Reversed = ToReverse
- ToReverse = nextToReverse
- nextToReverse = toReverse.next
- toReverse.next = Reverse.addr or None
-
- Reversed = ToReverse
- ToReverse = nextToReverse
- nextToReverse = toReverse.next
- toReverse.next = Reverse.addr or None
"""
reversed = None
toReverse = self.head
nextToReverse = toReverse.next_node
toReverse.next_node = reversed
self.tail = toReverse
while nextToReverse != None:
# print(f"reversed: {reversed}, toReverse: {toReverse}, nextToReverse: {nextToReverse}")
reversed = toReverse
toReverse = nextToReverse
nextToReverse = toReverse.next_node
toReverse.next_node = reversed
self.head = toReverse
print("Hello World!")
myLinkedList = LinkedList(5)
myLinkedList.append(10)
myLinkedList.append(15)
assert(myLinkedList.get_head() == 5)
assert(myLinkedList.get_tail() == 15)
assert(myLinkedList.get_position(1) == 10)
myLinkedList.append(20)
assert(myLinkedList.get_position(3) == 20)
assert(myLinkedList.get_position(4) == None)
myLinkedList.prepend(2)
assert(myLinkedList.get_position(0) == 2)
assert(myLinkedList.get_head() == 2)
assert(myLinkedList.get_position(0) == 2)
myLinkedList.insert(value=7,position=2)
myLinkedList.printLinkedList()
assert(myLinkedList.get_position(2) == 7)
print("reverse: ")
myLinkedList.reverse()
myLinkedList.printLinkedList()
assert(myLinkedList.get_position(0) == 20)
assert(myLinkedList.get_position(4) == 5)
assert(myLinkedList.get_position(5) == 2)
print("Good-bye Cruel World")
Python
INFO