Python中链表的排序链表（Sort List）操作

2023-04-11 00:00:00 操作 排序 链表

链表的排序通常采用快速排序或归并排序的方法。

其中，归并排序比较适合链表的排序操作。

具体步骤如下：

  1. 找到链表的中点，将链表拆分为左右两部分。

  2. 对左右两部分分别进行递归排序。

  3. 将两个有序链表合并成一个有序链表。

下面是Python代码实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def find_middle(head):
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    return mid

def merge(left, right):
    dummy = tail = ListNode()
    while left and right:
        if left.val < right.val:
            tail.next, left = left, left.next
        else:
            tail.next, right = right, right.next
        tail = tail.next
    tail.next = left or right
    return dummy.next

def sort_list(head):
    if not head or not head.next:
        return head
    mid = find_middle(head)
    left = sort_list(head)
    right = sort_list(mid)
    return merge(left, right)

例如，对以下链表排序：

1 -> 5 -> 3 -> 2 -> 4 -> None

排序后的链表为：

1 -> 2 -> 3 -> 4 -> 5 -> None

完整代码和范例：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def print_list(head):
    while head:
        print(head.val, end=' -> ')
        head = head.next
    print('None')

def find_middle(head):
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    return mid

def merge(left, right):
    dummy = tail = ListNode()
    while left and right:
        if left.val < right.val:
            tail.next, left = left, left.next
        else:
            tail.next, right = right, right.next
        tail = tail.next
    tail.next = left or right
    return dummy.next

def sort_list(head):
    if not head or not head.next:
        return head
    mid = find_middle(head)
    left = sort_list(head)
    right = sort_list(mid)
    return merge(left, right)

if __name__ == '__main__':
    # 创建链表
    n5 = ListNode(4)
    n4 = ListNode(2, n5)
    n3 = ListNode(3, n4)
    n2 = ListNode(5, n3)
    n1 = ListNode(1, n2)
    head = n1

    # 打印原始链表
    print('原始链表：')
    print_list(head)

    # 排序链表
    head = sort_list(head)

    # 打印排序后的链表
    print('排序后的链表：')
    print_list(head)

输出：

原始链表：
1 -> 5 -> 3 -> 2 -> 4 -> None
排序后的链表：
1 -> 2 -> 3 -> 4 -> 5 -> None

相关文章