本文主要是介绍[LeetCode] 148. Sort List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目内容
https://leetcode-cn.com/problems/sort-list/
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:输入: 4->2->1->3
输出: 1->2->3->4
示例 2:输入: -1->5->3->4->0
输出: -1->0->3->4->5题目思路
这道题目根据这种空间和时间复杂度的要求下，我使用了二路归并的方法。那么对于二路归并来说，需要先创建二路，然后进行归并。针对于递归停止，我设置了两种可能的情况。第一种是只有一个节点，直接返回就可以。第二种是有两个节点，排序后返回就可以。除非一开始就是一个空链表，否则不可能出现没有节点的情况，都可以分解为只有一个或者只有两个节点的情况。
然后当包含三个或者三个以上的节点时，我们使用快慢指针的方式进行划分，慢指针来做第二个链表的开头，注意断链。之后就使用了两两归并的方法组合即可。整个程序的思路可以看做先是递归的把链表拆成1个或者2个子链表的形式，然后再归并（有点像DFS树），然后再拆右侧的，最后整体归并。
程序代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution(object):def sortList(self, head):""":type head: ListNode:rtype: ListNode"""if not head:return headelse:return self.calculate(head)def calculate(self,head):if not head.next:#only 1 nodereturn headif not head.next.next:# only 2 nodeif head.val>head.next.val:head.val,head.next.val=head.next.val,head.valreturn headpre,slow,fast=None,head,headwhile fast and fast.next:pre=slowfast=fast.next.nextslow=slow.nextpre.next=None#cut off lst1lst1=self.calculate(head)lst2=self.calculate(slow)new_head=ListNode(0)cur=new_headwhile lst1 and lst2:if lst1.val<lst2.val:cur.next=lst1lst1=lst1.nextelse:cur.next=lst2lst2=lst2.nextcur=cur.nextif not lst1:cur.next=lst2else:cur.next=lst1return new_head.next
这篇关于[LeetCode] 148. Sort List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
