Python中链表的排序算法及其实现
Python中链表的排序算法主要有插入排序、选择排序和归并排序等，以下是它们的实现方式和代码演示。
- 插入排序
插入排序的思路很简单，就是将链表中的每一个元素插入到已排序的列表中，并最终得到完全有序的链表。具体实现时，可以使用一个哨兵节点作为有序列表的头部节点，然后从原始链表的第一个节点开始遍历，每遍历到一个节点，就将其插入到有序列表中。
代码演示：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def insertionSortList(head: ListNode) -> ListNode: if not head or not head.next: return head dummy = ListNode(-1) dummy.next = head last_sorted = head curr = head.next while curr: if last_sorted.val <= curr.val: last_sorted = last_sorted.next else: prev = dummy while prev.next.val <= curr.val: prev = prev.next last_sorted.next = curr.next curr.next = prev.next prev.next = curr curr = last_sorted.next return dummy.next
- 选择排序
选择排序的思路是循环遍历链表，每次找到未排序部分中最小的节点，然后将其放到有序部分的末尾。具体实现时，需要维护一个已排好序部分的头部节点，初始为空，并将这个节点的next指向原始链表的头部节点，然后每次找到剩余未排序部分中最小的节点，并将其插入到已排序部分的末尾。
代码演示：
def selectionSortList(head: ListNode) -> ListNode: if not head or not head.next: return head dummy = ListNode(-1) dummy.next = head sorted_tail = dummy while sorted_tail.next: min_node_prev = sorted_tail min_node = sorted_tail.next curr = sorted_tail.next while curr: if curr.val < min_node.val: min_node = curr min_node_prev = sorted_tail curr = curr.next min_node_prev.next = min_node.next min_node.next = sorted_tail.next sorted_tail.next = min_node sorted_tail = sorted_tail.next return dummy.next
- 归并排序
归并排序是一种非常高效的排序算法，它的思想是将链表分成两个部分，对每个部分进行递归调用归并排序，然后将两个已经排序的链表合并成一个链表。具体实现时，可以使用快慢指针将链表分成两个部分，然后递归调用归并排序，并将两个已经排序的链表合并成一个链表。
代码演示：
def mergeSortList(head: ListNode) -> ListNode: if not head or not head.next: return head mid = findMid(head) right_head = mid.next mid.next = None return merge(mergeSortList(head), mergeSortList(right_head)) def findMid(head: ListNode): slow = head fast = head.next while fast and fast.next: slow = slow.next fast = fast.next.next return slow def merge(left: ListNode, right: ListNode): dummy = ListNode(-1) curr = dummy while left and right: if left.val <= right.val: curr.next = left left = left.next else: curr.next = right right = right.next curr = curr.next if left: curr.next = left if right: curr.next = right return dummy.next
相关文章