103 lines
2.6 KiB
Python
103 lines
2.6 KiB
Python
class ListNode:
|
|
def __init__(self, item):
|
|
self.item = item
|
|
self.next = None
|
|
|
|
class LinkedList:
|
|
def __init__(self):
|
|
self.size = 0
|
|
self.head = None
|
|
|
|
def printList(self):
|
|
cur = self.head
|
|
if not cur:
|
|
print("Empty")
|
|
return
|
|
while cur:
|
|
print(cur.item, end=" ")
|
|
cur = cur.next
|
|
print()
|
|
|
|
def removeAllItems(self):
|
|
self.head = None
|
|
self.size = 0
|
|
|
|
def findNode(self, index):
|
|
if index < 0 or index >= self.size:
|
|
return None
|
|
cur = self.head
|
|
while index > 0:
|
|
cur = cur.next
|
|
index -= 1
|
|
return cur
|
|
|
|
def insertNode(self, index, value):
|
|
if index < 0 or index > self.size:
|
|
return -1
|
|
|
|
newNode = ListNode(value)
|
|
if index == 0: # Insert at the beginning
|
|
newNode.next = self.head
|
|
self.head = newNode
|
|
else:
|
|
prev = self.findNode(index - 1)
|
|
newNode.next = prev.next
|
|
prev.next = newNode
|
|
|
|
self.size += 1
|
|
return 0
|
|
|
|
def removeNode(self, index):
|
|
if index < 0 or index >= self.size:
|
|
return -1
|
|
|
|
if index == 0: # Remove the first node
|
|
self.head = self.head.next
|
|
else:
|
|
prev = self.findNode(index - 1)
|
|
prev.next = prev.next.next
|
|
|
|
self.size -= 1
|
|
return 0
|
|
|
|
def moveEvenItemsToBack(ll):
|
|
if ll.size < 2:
|
|
return
|
|
|
|
cur = ll.head
|
|
index = 0
|
|
for _ in range(ll.size):
|
|
if cur.item % 2 == 0:
|
|
even_value = cur.item
|
|
cur = cur.next
|
|
ll.removeNode(index)
|
|
ll.insertNode(ll.size, even_value)
|
|
else:
|
|
cur = cur.next
|
|
index += 1
|
|
|
|
if __name__ == "__main__":
|
|
ll = LinkedList()
|
|
|
|
while True:
|
|
print("1: Insert an integer to the linked list:")
|
|
print("2: Move all even integers to the back of the linked list:")
|
|
print("0: Quit:")
|
|
|
|
choice = int(input("Please input your choice (1/2/0): "))
|
|
|
|
if choice == 1:
|
|
value = int(input("Input an integer that you want to add to the linked list: "))
|
|
ll.insertNode(ll.size, value)
|
|
print("The resulting linked list is:")
|
|
ll.printList()
|
|
elif choice == 2:
|
|
moveEvenItemsToBack(ll)
|
|
print("The resulting linked list after moving even integers to the back is:")
|
|
ll.printList()
|
|
elif choice == 0:
|
|
ll.removeAllItems()
|
|
break
|
|
else:
|
|
print("Choice unknown;")
|