Блог

Главная - Вопросы по программированию - Сортировка односвязного списка с использованием сортировки по вставке в python

Сортировка односвязного списка с использованием сортировки по вставке в python

#python #sorting #data-structures #linked-list #insertion-sort

#питон #сортировка #структуры данных #связанный список #вставка-сортировка

Вопрос:

Я новичок в python, который выходит из c , я не знаю, как работать со связанным списком без указателей, при этом я написал этот код, но он возвращает тот же список, не сортируя его вообще

 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

Комментарии:

1. Требуется ли вам реализовать связанный список? Вы можете использовать list встроенный Python.

2. да, я должен использовать односвязный список!

3. в python, в отличие от c , list это не связанный список, collections.deque это двойной связанный список

Ответ №1:

Вы не увеличиваете переменную узла цикла. Ваш код выходит из внутреннего цикла while до того, как переменная узла цикла получит возможность увеличения loop=loop.next . Вот мое решение, я разделил классы Node и Linked List. Настройте переменную длины и увеличивайте значение каждый раз, когда я вставлял узел. Затем использовал обычный метод сортировки по вставке.

 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
Метки: