Объект ListNode не повторяется - PullRequest
Новая
       21

Объект ListNode не повторяется

0 голосов
/ 03 сентября 2018

Я практикую свои навыки программирования на Linkcode. Я делаю проблему отсортированного списка, в которой мне нужно отсортировать связанный список за O (n log n) времени, используя постоянную сложность пространства. Я хочу использовать алгоритм быстрой сортировки, чтобы сделать это.

Я получил сообщение об ошибке: "Traceback (последний вызов был последним): файл" /code/Main.py ", строка 20, в файле ans = solution.sortList (head)" /code/Solution.py ", строка 21, в манекене sortList, tail = self.quickSort (head) Файл "/code/Solution.py", строка 91, в манекене quickSort, tail1 = self.quickSort (start) TypeError: объект ListNode не повторяется " Я действительно сбит с толку, потому что я не использую ничего для повторяемости в строке 91. Я просто передаю объект 'listNode' в рекурсивную функцию, которая запрашивает ввод 'listNode'. Может кто-нибудь помочь мне понять, в чем проблема?

вот мой код: 

"""
Definition of ListNode
class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""

# quicksorting
class Solution:
    """
    @param head: The head of linked list.
    @return: You should return the head of the sorted linked list, using constant space complexity.
    """
    def sortList(self, head):
        # write your code here
        if not head:
            return None
        if head.next is None:
            return head
        dummy, tail = self.quickSort(head)
        return dummy.next

    def quickSort(self, start):
        dummy = ListNode(0)
        dummy.next = start

        if not start:
            return None 
        if start.next is None:
            return start

        slow = start
        fast = start.next

        while fast:
            if fast.next:
                fast = fast.next.next
                slow = slow.next
            else:
                break

        mid = slow
        pivot = mid.val 

        left = start
        leftPrev = dummy
        right = mid.next
        rightPrev = mid
        Tail = mid

        while left != mid and right:
            while left != mid and left.val < pivot:
                left = left.next
                leftPrev = leftPrev.next
            while right and right.val > pivot:
                Tail = Tail.next
                right = right.next 
                rightPrev = rightPrev.next

            if left != mid and right:
                self.changeNode(left, right, leftPrev, rightPrev)

                temp = left 
                left = right 
                right = temp

        while left != mid:
            if left.val <= pivot:
                left = left.next
                leftPrev = leftPrev.next
            else:
                nextLeft = left.next
                self.insertNode(left, Tail, leftPrev)

                Tail = Tail.next 
                left = nextLeft

        while right:
            if right.val >= pivot:
                right = right.next 
                rightPrev = rightPrev.next
                Tail = Tail.next
            else:
                nextRight = right.next
                self.insertNode(right, dummy, rightPrev)
                right = nextRight

        midNext = mid.next
        mid.next = None
        dummy1, tail1 = self.quickSort(start)
        dummy2, tail2 = self.quickSort(mid)

        dummy.next = dummy1.next
        tail1.next = dummy2.next 
        tail2.next = None

        return dummy, Tail

    # insert node2 to node1.next of a list
    def insertNode(self, node1, node2, prevNode2):
        nextNode2 = node2.next
        node2.next = node1.next
        node1.next = node2
        prevNode2.next = nextNode2

    # exchange position of node1 and node2 of a list
    def changeNode(self, node1, node2, prevNode1, prevNode2):
        nextNode2 = node2.next
        prevNode1.next = node2
        node2.next = node1.next
        prevNode2.next = node1 
        node1.next = nextNode2

1 Ответ

0 голосов
/ 03 сентября 2018

Ваш метод quickSort должен возвращать tuple (который является итеративным), как вы делаете внизу с return dummy, Tail, так что множественное присваивание 

 dummy1, tail1 = self.quickSort(start)  
 # return value must be iterable (producing exactly two elements)!

может работать. В двух if-блоках в верхней части указанного метода 

if not start:
    return None   # not iterable!
if start.next is None:
    return start  # not iterable!

однако вы возвращаете None или start (оба из которых не повторяемы), для которых вышеупомянутое присваивание завершится с ошибкой, которую вы видите.

...