2 
def sublist(head):
    current=head
    #temp=current #If my list is 3->2->1->4->5->6 it goes into an infinite loop
    while ((current.next is not None) and current.value < current.next.value ):
        temp=current
        current=current.next
    start=current
    while ((current.next is not None) and current.value > current.next.value ):
        current=current.next
    last=current.next
    current.next=None
    first=reverse_linked_list(start)
    temp.next=first

    while first.next is not None:
        first=first.next
    first.next=last

    while head:
        print head.value
        head=head.next
    return head

代码的工作：我将代码的输入作为无序子列表提供，其中列表中的子列表按降序排列，而链表的其余部分按升序排列。

该代码适用于 1、2、3、4、5、9、8、7、10 和 1、10、9、8、7、6、5 等输入，即中间和末尾的未排序列表，但如果列表在开头未对 3、2、1、4、5、6 等输入进行排序，则它不起作用！谁能帮帮我请..

4

1 回答 1

1

我无法弄清楚您的代码，但我怀疑无限循环的原因是您设置temp为current而不是current.value，因此您正在翻转 cons 单元格本身而不是它们的内容。这可能是在创建您无限迭代的循环链接列表。

但是，我会这样做（使用基本的冒泡排序算法）：

from functools import total_ordering

@total_ordering
class cons:
    def __init__(self, head, tail=None):
        self.head = head
        self.tail = tail

    @classmethod
    def fromlist(self, l):
        if l == []:
            return None
        return cons(l[0], cons.fromlist(l[1:]))

    def tolist(self):
        if self.tail == None:
            return [self.head]
        else:
            return [self.head] + self.tail.tolist()

    def flip(self):
        if not self.tail == None:
            tmp = self.head
            self.head = self.tail.head
            self.tail.head = tmp

    def __lt__(self, other):
        if other == None:
            return True
        else: 
            return self.head < other.head
    def __eq__(self, other):
        if other == None:
            return False
        else:
            return self.head == other.head

def llsort(head):
    changed = True
    while changed:
        changed = False
        current = head
        while current != None:
            if current > current.tail:
                current.flip()
                changed = True
            current = current.tail

编辑：__lt__andflip不适用于其他用途。事实上，我只是把__lt__and放在__eq__那里，因为我试图找出一种方法来使用 python 的内置排序系统之一，但无法让它工作。为了简化一点：

class cons:
    def __init__(self, head, tail=None):
        self.head = head
        self.tail = tail

    def flip(self):
        if not self.tail == None:
            tmp = self.head
            self.head = self.tail.head
            self.tail.head = tmp


def llsort(head):
    changed = True
    while changed:
        changed = False
        current = head
        while current.tail != None:
            if current.head > current.tail.head:
                current.flip()
                changed = True
            current = current.tail
于 2013-05-25T19:23:10.280 回答