使用 Python 将新值插入排序链表?

Question

>我实现了以下代码，它可以工作，但它在链表的末尾添加了新值 喜欢，[1,2,3,6]，值 4 结果是 [1,2,3,6,4] 这是错误的 正确结果为 [1,2,3,4,6]

# Singly-linked lists are already defined with this interface:
class ListNode(object):
def __init__(self, x):
self.value = x
self.next = None
def insertValueIntoSortedLinkedList(head, valuetoInsert):
currentNode = head
while currentNode is not None:
if currentNode.next is None:
currentNode.next = ListNode(valuetoInsert)
return head
currentNode = currentNode.next

我的问题如何修改插入值到排序链接列表函数 谢谢

Answer 1

我对insertValueIntoSortedLinkedList()进行了一些更改。基本上，错误在于您不比较要插入的值是否小于当前值(因此您始终将新值插入到末尾(。

# Singly-linked lists are already defined with this interface:
class ListNode(object):
def __init__(self, x):
self.value = x
self.next = None
def insertValueIntoSortedLinkedList(head, valuetoInsert):
currentNode = head
while True:
# is current value greater than value we are going to insert?
if currentNode.value > valuetoInsert:
# yes, create new node with old value
next_node = ListNode(currentNode.value)
next_node.next = currentNode.next
# replace current value with new value (which is lower than old value)
currentNode.value = valuetoInsert
# set next node to new node we created previously (with old value)
currentNode.next = next_node
# we are done, return
return
# we are at the end, so break from while-loop
if currentNode.next is None:
break
currentNode = currentNode.next
# the valuetoInsert is greater than all values so far, so insert it to the end
currentNode.next = ListNode(valuetoInsert)
def print_list(head):
""" Helper method to print the list """
currentNode = head
while currentNode is not None:
print(currentNode.value)
currentNode = currentNode.next
l = ListNode(1)
insertValueIntoSortedLinkedList(l, 2)
insertValueIntoSortedLinkedList(l, 3)
insertValueIntoSortedLinkedList(l, 6)
insertValueIntoSortedLinkedList(l, 4)  # this inserts value before 6
print_list(l)

指纹：

1
2
3
4
6