我需要定義insert_in_ascending_order()方法，我不知道我在做什么。我需要代碼做的是輸入：
例如：
8 3 6 2 5 9 4 1 7
和輸出：
1 2 3 4 5 6 7 8 9
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, new_node):
if self.head == None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
def prepend(self, new_node):
if self.head == None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
def insert_after(self, current_node, new_node):
if self.head == None:
self.head = new_node
self.tail = new_node
elif current_node is self.tail:
self.tail.next = new_node
self.tail = new_node
else:
new_node.next = current_node.next
current_node.next = new_node
# TODO: Write insert_in_ascending_order() method
def insert_in_ascending_order(self, new_node):
if self.head is None:
new_node.next = self.head
self.head = new_node
elif self.head.data >= new_node.data:
new_node.next = self.head
self.head = new_node
else :
current = self.head
current = self.head
while current is not None:
print (current.data)
current = current.next
new_node = current
current = new_node
uj5u.com熱心網友回復：
您可以讓您現有的方法為您完成大部分作業。
如果您認為您的頭部將是最小值，而您的尾部將是最大的。您可以從頭到尾遍歷，直到到達插入點。
如果一開始你會處理一些邊緣情況。
def insert_in_ascending_order(self, new_node):
# the linked list is empty. just append and return
if self.head is None:
self.append(new_node)
return
# the linked list head value is larger than the current value.
# meaning our new_node value is the smallest in the list
# just prepend and return
if new_node.data < self.head.data:
self.prepend(new_node)
return
# now you know can assume everything is sorted
# and start at the head, your smallest value
# and move forward from that
current = self.head
while True:
# we've reached our tail.
# let our append method do the work
# and break from the loop
if current.next is None:
self.append(new_node)
break
# we've reached our insert point
# insert and break
if new_node.data < current.next.data:
# make the insert points next, our new_nodes next
new_node.next = current.next
# and exchange it with our new_node
current.next = new_node
break
# continue on
current = current.next
這是完整的代碼，帶有一個不錯的repr.
class Node:
def __init__(self, value):
self.data = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, new_node):
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
def prepend(self, new_node):
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
def insert_in_ascending_order(self, new_node):
if self.head is None:
self.append(new_node)
return
if new_node.data < self.head.data:
self.prepend(new_node)
return
current = self.head
while True:
if current.next is None:
self.append(new_node)
break
if new_node.data < current.next.data:
insert_point_next = current.next
new_node.next = insert_point_next
current.next = new_node
break
current = current.next
def __repr__(self):
_repr = '['
current = self.head
while current is not None:
_repr = f'{_repr}{repr(current.data)}, '
current = current.next
if _repr.endswith(', '):
_repr = _repr[:-2]
return f'{_repr}]'
lst = LinkedList()
for i in [8, 3, 6, 2, 5, 9, 4, 1, 7]:
lst.insert_in_ascending_order(Node(i))
print(lst) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
uj5u.com熱心網友回復：
您需要跟蹤將成為您要插入的節點的前任節點，同時尋找將成為其后繼節點的節點。
# start with first node in list
prevNode = None
nextNode = self.head
# find adjacent nodes
while nextNode and nextNode.data < newNode.data:
prevNode,nextNode = nextNode,nextNode.next
# link to new node
if prevNode: prevNode.next = newNode # insert after
else: self.head = newNode # new head
# chain to successor
newNode.next = nextNode
if not nextNode: self.tail = newNode # new tail
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/404916.html
標籤：