根据字符串值将整个链表按升序排序- Python

Question

我一直在尝试在Python中实现一个链表，并根据链表中存在的字符串值对其进行排序。

我正在尝试使用冒泡排序逻辑，下面的函数是我想到的:

def sort_linked_list(self):

temp = self.head_node
if(temp == None) | (temp.next == None):
return
while(temp is not None):
if(temp.song.song_name > temp.song.song_name):
prev = temp
temp = temp.next
temp.next = prev
temp = temp.next
return

不幸的是，这遍历了链表中的前两个值，并且陷入了无限循环。我对链表很陌生，因此可能在这个循环中犯了一些我无法识别的基本错误。

任何帮助都是感激的。请在解决方案中加上解释，以便我能理解。

链表部分代码:

class Song:
def __init__(self, song_id, song_name, song_length):
self.song_id = song_id
self.song_name = song_name
self.song_length = song_length

def __str__(self):
return str({'song_id':self.song_id, 
'song_name':self.song_name, 
'song_length':self.song_length})

# Node for each of teh cong object that is going to be created. 
# Each of these node will contain the song data nd reference to the next element
class ListNode:
def __init__(self, song:Song):
self.song = song
self.next = None

def __str__(self):
return str(self.song)

# Linked list class that will be used to do the various operations
# Insert, create, delete, traversal of the linked list
# Few other operation such as 
# a. deletion of song, 
# b. sorting a linked list based on song 
# c. randomly picking a song for playing
class LinkedList:
def __init__(self):
self.head_node = None
self.count = 0

# Traversing the linked lists
def traversal(self):
if self.head_node is None:
return

temp_node = self.head_node

while(temp_node != None):
print(temp_node.song)
time.sleep(2)
temp_node = temp_node.next

time.sleep(2)

return

# insertion of the node in the beginning of the linked lists
def insert_at_start(self, node):
if self.head_node is None:
self.head_node = node
self.count = self.count + 1
return True

node.next = self.head_node
self.head_node = node

return True

# insertion of the node after a particular song    
def insert_after(self, song_name, node):
temp_node = self.head_node

# Checking till we find the song_name we are looking for
while(temp_node.song.song_name!=song_name):
temp_node = temp_node.next

# if song is not found  
if temp_node is None:
return False
# if song is found
else:
# Chckinhg if it is the last node
if temp_node.next == None:
temp_node.next = node
# If it is not the last node
else:
node.next = temp_node.next
temp_node.next = node

return True

# insertion of the node before a particular song in the linked lists    
def insert_before(self, song_name, node):
temp_node = self.head_node
prev_node = None

# Checking till we find the song_name we are looking for
while(temp_node.song.song_name!=song_name):
prev_node = temp_node
temp_node = temp_node.next

# if song is not found  
if temp_node == None:
return False
# if list has only one song
if prev_node == None:
node.next = self.head_node
self.head_node = node
return True

# updating the linked list and inserting the data
prev_node.next = node
node.next = temp_node

return True

Answer 1

你的尝试有几个问题:

• 算法对每个节点只进行一次访问。不可能在一次扫描中对列表进行排序。冒泡排序需要两个循环(嵌套)。只要内部循环必须进行交换，外部循环就会一直循环下去。一旦内部循环没有找到任何要交换的对，则对列表进行排序，外部循环可以停止。

• 两个相邻节点的交换通常需要两个引用进行更改。位于之前的节点的next属性也需要更改，而您的代码没有这样做。

• 排序可能意味着最初是头节点的东西不再位于头部，因此您的代码必须预见到对self.head_node的赋值…或者"已排序";Version将始终以排序前相同的节点开始。

我建议首先创建一个虚拟节点，位于头节点之前的。这有助于在需要交换头节点时简化代码。在这种情况下，假人的next属性将改变，就像任何其他节点的next可以改变一样。当所有这些都完成后，我们就可以读取假节点后面的节点，并使其成为新的头节点。

def sort_linked_list(self):
sentinel = ListNode(None)
sentinel.next = self.head_node

dirty = True
while dirty: # Repeat until the inner loop finds nothing to swap
dirty = False
node = sentinel
# keep comparing the pair that follows after(!) `node`
while node.next and node.next.next:
first = node.next
second = first.next
if first.song.song_name > second.song.song_name:
# A swap needs to set two(!) next attributes
node.next = second
first.next = second.next
second.next = first
dirty = True  # Indicate that the outer loop needs another iteration
node = node.next

# Make sure the head node references the right node after sorting
self.head_node = sentinel.next

下面是一个演示，它快速地用你的类创建一些节点，然后运行上面的方法，最后遍历排序列表:

# Your code without change, except in the `sort_linked_list` method
class Song:
def __init__(self, song_id, song_name, song_length):
self.song_id = song_id
self.song_name = song_name
self.song_length = song_length

def __str__(self):
return str({'song_id':self.song_id, 
'song_name':self.song_name, 
'song_length':self.song_length})

class ListNode:
def __init__(self, song:Song):
self.song = song
self.next = None

def __str__(self):
return str(self.song)

class LinkedList:
def __init__(self):
self.head_node = None
self.count = 0

def traversal(self):
if self.head_node is None:
return
temp_node = self.head_node
while(temp_node != None):
print(temp_node.song)
temp_node = temp_node.next
return

def insert_at_start(self, node):
if self.head_node is None:
self.head_node = node
self.count = self.count + 1
return True
node.next = self.head_node
self.head_node = node
return True

def sort_linked_list(self):
sentinel = ListNode(None)
sentinel.next = self.head_node

dirty = True
while dirty: # Repeat until the inner loop finds nothing to swap
dirty = False
node = sentinel
# keep comparing the pair that follows after(!) `node`
while node.next and node.next.next:
first = node.next
second = first.next
if first.song.song_name > second.song.song_name:
# A swap needs to set two(!) next attributes
node.next = second
first.next = second.next
second.next = first
dirty = True  # Indicate that the outer loop needs another iteration
node = node.next

# Make sure the head node references the right node after sorting
self.head_node = sentinel.next

# Demo 
titles = [
"Smells Like Teen Spirit",
"Billie Jean",
"Stayin’ Alive",
"I Will Survive",
"Whole Lotta Love",
"Sweet Child O’Mine",
"Scream and Shout",
"Santeria",
"Alright",
"Thrift Shop"
]
lst = LinkedList()
for i, title in enumerate(titles):
lst.insert_at_start(ListNode(Song(i, title, len(title))))
lst.sort_linked_list()
lst.traversal()  # Outputs the 10 songs in sorted order