Сортировать связанный список, обрабатывая пары как один элемент - PullRequest
Новая
       48

Сортировать связанный список, обрабатывая пары как один элемент

0 голосов
/ 18 февраля 2020

Я работаю над этим испытанием:

Сортировка связанного списка в порядке возрастания, рассматривая два узла как два числа git. (сортировка по месту)

4 ≤ n ≤ 1000

Длина связанного списка всегда четная.

Пример 1:

Вход
1 → 3 → 4 → 2 → 1 → 2

Выход
1 → 2 → 1 → 3 → 4 → 2

Пояснение:
12> 13> 42

Пример 2:

Вход
1 → 3 → 0 → 3

Выход
0 → 3 → 1 → 3

Вот моя реализация шаблона связанного списка; который любой может начать кодировать: 

 class Node():
    def __init__(self,val):
        self.data = val
        self.next = None

 class Linkedlist():
    def __init__(self):
        self.head = None

    def add(self,x):
        t = Node(x)
        t.next = self.head
        self.head = t

    def display(self):
        p = self.head
        while p != None:
            print(p.data)
            p=p.next

    def sort(self):
        curr = self.head
        # your logic here

m = Linkedlist()
m.add(1)
m.add(3)
m.add(4)
m.add(2)
m.add(1)
m.add(2)
m.display()

Какой алгоритм сортирует пары в связанном списке (на месте) и как его кодировать?

Ответы [ 2 ]

1 голос
/ 18 февраля 2020

Сначала напишите функцию, которая принимает связанный список отдельных узлов di git и объединяет каждую пару смежных отдельных узлов di git в связанный список вдвое меньше узлов, где каждый узел содержит двойное число di * 1010. * число.

Затем сортируйте полученный связанный список, используя пузырьковую сортировку, которая является O (n ^ 2), или сортировку слиянием, которая является O (nlogn).

Затем, если необходимо, написать третью функцию, которая разбирает двойные узлы di git и создает новый список из вдвое большего числа одиночных узлов di git.

Выполнение этого с двумя или тремя такими функциями действительно упростит сортировку .

0 голосов
/ 18 февраля 2020

Прежде всего, ваш текущий код будет генерировать не список 1 → 3 → 4 → 2 → 1 → 2, а его инверсию. Это потому, что ваше определение метода add добавит заданное значение к списку.

Чтобы заставить add работать правильно, он должен сначала найти последний узел в списке и добавьте новый узел после него. Поскольку это не очень эффективный метод добавления множества значений в список, я бы предложил также определить add как метод Node и разрешить цепочку вызовов add. Таким образом, вы можете добавить много значений в одно цепочечное выражение, не будучи неэффективным.

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

Наконец, для самого алгоритма sort вы можете сократить список только до его первой пары (что тогда очевидно отсортировано), а остальное обрабатывается как отдельный список несортированных узлов. Затем извлеките пару за раз из несортированного списка и найдите подходящее место для добавления ее в основной список, чтобы она оставалась отсортированной.

Этот процесс представляет O (n²) сложность времени в среднем и в худшем случае. Наилучшим случаем является O (n) , который возникает, когда список изначально отсортирован в обратном порядке.

Вот как это может выглядеть: 

class Node():
    def __init__(self, val):
        self.data = val
        self.next = None

    # Easy chaining: defining this method on a Node as well
    def add(self, val):
        node = Node(val)
        node.next = self.next
        self.next = node
        return node

    # Define how the value of a pair is calculated
    def pairvalue(self):
        return self.data * 10 + self.next.data

class Linkedlist():
    def __init__(self):
        self.head = None

    def add(self, val):
        # Corrected method: addition should be at the end of the list
        node = Node(val)
        if not self.head:
            self.head = node
        else: # Look for the last node in the list
            curr = self.head
            while curr.next:
                curr = curr.next
            # ...and append the new node after it
            curr.next = node
        return node # Allow for chaining

    def display(self):
        p = self.head
        while p:
            print(p.data,  end= "→")
            p = p.next
        print("NIL")

    def sort(self):
        if not self.head:
            return
        # Reduce list to just its first pair
        # The remainder is a temporary "todo" list
        todo = self.head.next.next
        self.head.next.next = None

        while todo:
            pair = todo # The pair that will be added to the sorted list
            todo = todo.next.next
            val = pair.pairvalue()
            if val < self.head.pairvalue():
                # The pair is a minimum: prepend it
                pair.next.next = self.head
                self.head = pair
            else:
                curr = self.head.next # odd index
                # Find insertion point in sorted list
                while curr.next and curr.next.pairvalue() < val:
                    curr = curr.next.next
                # Perform insertion
                pair.next.next = curr.next
                curr.next = pair

m = Linkedlist()
m.add(1).add(3).add(4).add(2).add(1).add(2)
m.display() # original list
m.sort()
m.display() # final list

вывод: 

1→3→4→2→1→2→NIL
1→2→1→3→4→2→NIL
...