【Python】快速排序法 Leetcode 148. 排序链表

本文主要是介绍【Python】快速排序法 Leetcode 148. 排序链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

示例 1：
在这里插入图片描述

输入：head = [4,2,1,3]
输出：[1,2,3,4]

代码

第一次使用朴素快速排序，基准值为头节点值，居然超时了，然后又改进成了随机基准的快排，以下是两个版本的代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:return self.dfs(head)[0]#	朴素快速排序def dfs(self,head):if(not head): return None,Nonesmaller_dummy = ListNode(-1)smaller_node  = smaller_dummybigger_dummy = ListNode(-1)bigger_node  = bigger_dummynode = head.nextwhile(node):if(node.val > head.val):bigger_node.next = nodebigger_node = bigger_node.nextelse:smaller_node.next = nodesmaller_node = smaller_node.nextnode = node.nextsmaller_node.next = Nonebigger_node.next = Nonesmaller_head,smaller_tail = self.dfs(smaller_dummy.next)bigger_head,bigger_tail = self.dfs(bigger_dummy.next)if(smaller_head):smaller_tail.next = headhead.next = bigger_headreturn smaller_head,bigger_tail or headelse:head.next = bigger_headreturn head,bigger_tail or head

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def sortList(self, head):return self.dfs(head)[0]# 随机基准数的快排def dfs(self,head,low=-100000,high=100000):if(not head): return None,Nonesmaller_dummy = ListNode(-1)smaller_node  = smaller_dummybigger_dummy = ListNode(-1)bigger_node  = bigger_dummypivot_dummy  = ListNode(-1)pivot_node   = pivot_dummynode = headpivot_num = random.randint(low, high)while(node):if(node.val > pivot_num):bigger_node.next = nodebigger_node = bigger_node.nextelif(node.val < pivot_num):smaller_node.next = nodesmaller_node = smaller_node.nextelse:pivot_node.next = node    pivot_node = pivot_node.nextnode = node.nextsmaller_node.next = Nonebigger_node.next = Nonesmaller_head,smaller_tail = self.dfs(smaller_dummy.next,low,pivot_num)bigger_head,bigger_tail = self.dfs(bigger_dummy.next,pivot_num,high)if(pivot_dummy.next):if(smaller_head):smaller_tail.next = pivot_dummy.nextelse:smaller_head = pivot_dummy.nextsmaller_tail = pivot_nodeif(smaller_tail): smaller_tail.next = bigger_headreturn smaller_head or bigger_head,bigger_tail or smaller_tail