M148.排序链表

linked list, two pointers, divide and conquer, sorting, merge sort, https://leetcode.cn/problems/sort-list/

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 10^4] 内
-105 <= Node.val <= 10^5

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

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 or not head.next:
            return head
        
        # Helper function to find the middle of the linked list
        def find_middle(head):
            slow, fast = head, head.next
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        
        # Helper function to merge two sorted linked lists
        def merge(l1, l2):
            dummy = ListNode()
            tail = dummy
            while l1 and l2:
                if l1.val < l2.val:
                    tail.next = l1
                    l1 = l1.next
                else:
                    tail.next = l2
                    l2 = l2.next
                tail = tail.next
            tail.next = l1 if l1 else l2
            return dummy.next
        
        # Split the linked list into two halves
        mid = find_middle(head)
        right = mid.next
        mid.next = None
        left = head
        
        # Recursively sort each half
        left = self.sortList(left)
        right = self.sortList(right)
        
        # Merge the sorted halves
        return merge(left, right)

# Example usage
if __name__ == "__main__":
    def print_list(node):
        while node:
            print(node.val, end=" -> ")
            node = node.next
        print("None")
    
    # Create linked list [4, 2, 1, 3]
    head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
    sorted_head = Solution().sortList(head)
    print_list(sorted_head)  # Output: 1 -> 2 -> 3 -> 4 -> None

M148.排序链表 ​

M148.排序链表