题目描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例
输入：head = [4,2,1,3]
输出：[1,2,3,4]
题目难度：Medium
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list/
思路分析
常见的排序算法有选择排序，插入排序，快排， 归并排序，堆排序等。 由于可以快速得到链表的中间节点，我们考虑使用归并排序算法，两两排序，然后再合并。
链表中间节点的获取，可以采用快慢指针的方式，快指针一次移动两个节点，慢指针一次移动一个节点，当快指针走到链表尾部时，慢指针刚好指向链表的中间节点。
有序链表的合并可以参考：https://www.jianshu.com/p/6613df51fe36
以下是 Python 的代码实现
Python 实现
# 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: ListNode) -> ListNode:
if not head:
return
if not head.next:
return head
mid_node = self.mid_of_list(head)
head2 = mid_node.next
mid_node.next = None
new_head1 = self.sortList(head)
new_head2 = self.sortList(head2)
return self.merge(new_head1, new_head2)
def mid_of_list(self, head: ListNode):
p1 = head
p2 = head.next
while p2 and p2.next:
p1 = p1.next
p2 = p2.next.next
return p1
def merge(self, head1, head2):
dummy_node = new_head = ListNode(0, None)
while head1 and head2:
if head1.val < head2.val:
new_head.next = head1
head1 = head1.next
else:
new_head.next = head2
head2 = head2.next
new_head = new_head.next
if head1:
new_head.next = head1
if head2:
new_head.next = head2
return dummy_node.next
