題目描述

給你鏈表的頭結(jié)點(diǎn) head ，請(qǐng)將其按 升序 排列并返回 排序后的鏈表 。
示例
輸入：head = [4,2,1,3]
輸出：[1,2,3,4]

題目難度：Medium

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sort-list/

思路分析

常見(jiàn)的排序算法有選擇排序，插入排序，快排， 歸并排序，堆排序等。 由于可以快速得到鏈表的中間節(jié)點(diǎn)，我們考慮使用歸并排序算法，兩兩排序，然后再合并。
鏈表中間節(jié)點(diǎn)的獲取，可以采用快慢指針的方式，快指針一次移動(dòng)兩個(gè)節(jié)點(diǎn)，慢指針一次移動(dòng)一個(gè)節(jié)點(diǎn)，當(dāng)快指針走到鏈表尾部時(shí)，慢指針剛好指向鏈表的中間節(jié)點(diǎn)。
有序鏈表的合并可以參考：http://www.itdecent.cn/p/6613df51fe36

以下是 Python 的代碼實(shí)現(xiàn)

Python 實(shí)現(xiàn)

# 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