基于类构造的Python LinkedList元组排序求助（禁用内置函数）

Since you can't modify the original LinkedList class, convert to a list, or use built-in sorting functions, we'll implement MergeSort using standalone helper functions that work with the existing name, quantity, and tail attributes.

Key Steps #

MergeSort for linked lists relies on three core operations:

1. Split the list into two equal halves
2. Recursively sort each half
3. Merge the sorted halves back into one ordered list

1. Split the List #

Use the "tortoise and hare" method to find the midpoint and split the list:

def split_list(head):
    # Return if list is empty or has only one node
    if not head or not head.tail:
        return head, None
    
    slow = head  # Moves 1 step at a time
    fast = head.tail  # Moves 2 steps at a time
    
    while fast and fast.tail:
        slow = slow.tail
        fast = fast.tail.tail
    
    # Split the list at the midpoint
    second_half = slow.tail
    slow.tail = None
    return head, second_half

2. Merge Sorted Lists #

Combine two sorted lists into a single sorted list (defaults to sorting by quantity):

def merge_sorted_lists(left, right, key=lambda node: node.quantity):
    # Handle empty list cases
    if not left:
        return right
    if not right:
        return left
    
    # Initialize merged list with the smaller starting node
    if key(left) <= key(right):
        merged_head = left
        current = merged_head
        left = left.tail
    else:
        merged_head = right
        current = merged_head
        right = right.tail
    
    # Merge remaining nodes
    while left and right:
        if key(left) <= key(right):
            current.tail = left
            current = current.tail
            left = left.tail
        else:
            current.tail = right
            current = current.tail
            right = right.tail
    
    # Attach any remaining nodes from either list
    if left:
        current.tail = left
    if right:
        current.tail = right
    
    return merged_head

3. MergeSort Main Function #

Recursively split, sort, and merge the list:

def merge_sort(head, key=lambda node: node.quantity):
    # Base case: empty list or single node is already sorted
    if not head or not head.tail:
        return head
    
    # Split into two halves
    left, right = split_list(head)
    
    # Recursively sort each half
    sorted_left = merge_sort(left, key)
    sorted_right = merge_sort(right, key)
    
    # Merge sorted halves
    return merge_sorted_lists(sorted_left, sorted_right, key)

Helper Function to Print the List #

Verify results by printing the linked list:

def print_list(head):
    current = head
    while current:
        print(f"{current.name}: {current.quantity}", end=" -> ")
        current = current.tail
    print("None")

Usage Example #

Apply the sorting to your fruits list:

# Original list
print("Original List:")
print_list(fruits)

# Sort by quantity (default)
sorted_by_quantity = merge_sort(fruits)
print("\nSorted by Quantity:")
print_list(sorted_by_quantity)

# Sort by name instead
sorted_by_name = merge_sort(fruits, key=lambda node: node.name)
print("\nSorted by Name:")
print_list(sorted_by_name)

Output #

Original List:
Apples: 7 -> Bananas: 2 -> Dragon Fruit: 1 -> Pomelo: 14 -> Grapes: 65 -> Cherries: 43 -> Pears: 6 -> Mangoes: 31 -> None

Sorted by Quantity:
Dragon Fruit: 1 -> Bananas: 2 -> Pears: 6 -> Apples: 7 -> Pomelo: 14 -> Mangoes: 31 -> Cherries: 43 -> Grapes: 65 -> None

Sorted by Name:
Apples: 7 -> Bananas: 2 -> Cherries: 43 -> Dragon Fruit: 1 -> Grapes: 65 -> Mangoes: 31 -> Pears: 6 -> Pomelo: 14 -> None

内容的提问来源于stack exchange，提问作者danielMBell