在 python 中使用插入排序对单链表进行排序

Question

我是 python 的新手，即将从 C++ 开始，我不知道如何使用没有指针的链表，据说我已经编写了这段代码，但它 returns 相同完全不排序的列表

class ListNode:
    def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
def insertionSortList(head):
    if head.next==None:
        return head
    #checkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkks
    loop=head
    i=head
    while(i.next!=None):
        save_val=i.next
        i=i.next.next
        while True:
            if loop!=i and save_val.val>loop.val:
                loop=loop.next
            else:
                if loop==head:
                    save_val=loop
                    break
                else:
                    save_val=loop.next
                    loop=save_val
                    loop=head
                    break
    return head

Answer 1

您没有递增循环节点变量。在循环节点变量有机会递增 loop=loop.next 之前，您的代码会跳出内部 while 循环。这是我的解决方案，我将节点和链表分开类。设置一个长度变量并在每次插入节点时递增该值。然后使用正常的插入排序方法。

class Node:
  
    def __init__(self,value):
        self.value = value
        self.next = None
        
class ListNode:
    
    def __init__(self):
        self.head = None
        self.length = 0
        
    def __repr__(self):
        '''Allows user to print values in the ListNode'''  
        
        values = []
        current = self.head
        while current:
            values.append(current.value)
            current = current.next
        return ', '.join(str(value) for value in values)
    
    def insert(self,value):
        '''Inserts nodes into the ListNode class'''
        
        newNode = Node(value)
        if self.head is None:
            self.head = newNode
        else:
            newNode.next = self.head
            self.head = newNode
        self.length += 1
        return self
    
    def insertionSortList(self):
        '''Insertion sort method: held a temp variable and inserted the smallest value from temp through the rest of the list then incremented temp variable to the next idx/node'''
        
        current = self.head
        for _ in range(self.length-1):
            tempNode = current.next
            while tempNode:
                if tempNode.value < current.value:
                    current.value, tempNode.value = tempNode.value, current.value
                tempNode = tempNode.next
            current = current.next
        return self

在 python 中使用插入排序对单链表进行排序

Sorting singly linked list using insertion sort in python

python

sorting

data-structures

linked-list

insertion-sort