链表问题（6）-----排序
2021-05-17 03:30
标签：append not 思想 nbsp self lists info one none 采用一个数组来存储链表中的值，然后对该数组进行快排，然后再连成链表，快排思想如下图所示： 链表问题（6）-----排序 标签：append not 思想 nbsp self lists info one none 原文地址：https://www.cnblogs.com/Lee-yl/p/9747437.html一、题目：将单向链表按某值划分为左边小、中间相等、右边大的形式
简单的思路：时间O（N），空间O（N）
代码：
class Node:
def __init__(self,value):
self.value = value
self.next = None
#快排思想
def partition(arr,pivot):
small = -1
big = len(arr)
index = 0
while index != big:
if arr[index] pivot:
small += 1
arr[small] , arr[index] = arr[index] , arr[small]
index += 1
elif arr[index] == pivot:
index += 1
else:
big -= 1
arr[index] , arr[big] = arr[big] , arr[index]
return arr
#链表操作
def listSort(head,pivot):
if not head:
return head
#将链表存储在数组中
arr = []
while head:
arr.append(head.value)
head = head.next
arr = partition(arr,pivot)
#创建链表
node = Node(arr[0])
p = node
for i in range(1,len(arr)):
p.next = Node(arr[i])
p = p.next
return node
head = Node(9)
head.next = Node(0)
head.next.next = Node(4)
head.next.next.next = Node(3)
head.next.next.next.next = Node(1)
pivot = 3
node = listSort(head,pivot)
进阶思想：时间O（N），空间O（1）
代码：
class Node:
def __init__(self,value):
self.value = value
self.next = None
def listPartition(head,pivot):
if not head:
return head
sH = None
sT = None
eH = None
eT = None
bH = None
bT = None
while head:
next = head.next
head.next = None
if head.value pivot:
if not sH:
sH = head
sT = head
else:
sT.next = head
sT = head
elif head.value == pivot:
if not eH:
eH = head
eT = head
else:
eT.next = head
eT = head
else:
if bH == None:
bH = head
bT = head
else:
bT.next = head
bT = head
head = next
if sT:
sT.next = eH
eT = eT if eT else sT
if eT:
eT.next = bH
return sH if sH else eH if eH else bH
arr = [9,1,4,5,6,3,8]
head = Node(arr[0])
p = head
for i in range(1,len(arr)):
p.next = Node(arr[i])
p = p.next
pivot = 5
res = listPartition(head,pivot)
上一篇：python之yield表达式
下一篇：spring-mvc高级技术