148. 排序链表
已解答
中等
相关标签
相关企业
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def sortList(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
"""
# 排序至少是nlogn的，直接全部排序一个个连起来得了
# if head==None:
# return None
# arr=[]
# while head:
# arr.append(head)
# head=head.next
# arr.sort(key=lambda x:x.val)
# prev = ListNode(-1)
# for index ,node in enumerate(arr):
# prev.next = node
# prev = node
# # print(arr)
# arr[-1].next=None
# return arr[0]
# 这个面试的时候很难这么搞啊
# 这个merge的时候是左闭合，右开
return self.sortFunc(head,None)
def merge(self,list1,list2):
prev = ListNode(-1)
temp ,temp1, temp2 = prev , list1,list2
while temp1 and temp2:
if temp1.val<=temp2.val:
temp.next = temp1
temp1=temp1.next
else:
temp.next = temp2
temp2=temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return prev.next
# 如果两个都是空，return也是空
def sortFunc(self,head,tail):
# 利用快慢指针，得到mid，然后使用merge（左右两个递归的序列）
if not head:
return head
if head == tail:
return None
if head.next==tail:
head.next=None
return head
# 如果head是空，那就返回空
fast , slow = head,head
while fast!=tail:
fast = fast.next
slow = slow.next
if fast!=tail:
fast = fast.next
return self.merge(self.sortFunc(head,slow),self.sortFunc(slow,tail))
如果实际遇到的话，我直接来个放到arr里面
但是面试的话，我们这里直接是来个归并排序
