力扣热题100之排序链表

题目

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

代码

方法一：

用列表存值，然后再排序，最后遍历列表原地改值

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        head_list=[]
        dummy=ListNode(0,head)
        cur=dummy.next
        while cur:
            head_list.append(cur.val)
            cur=cur.next
        head_list.sort()
        i=0
        cur=dummy.next
        while cur:
            cur.val=head_list[i] 
            i+=1
            cur=cur.next
        return dummy.next       

方法二：

首先将原链表分为两段，然后分别通过递归合并对这两段链表进行排序，最后合并两段链表

# 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: Optional[ListNode]) -> Optional[ListNode]:
        def merge(left,right):
            dummy=ListNode(0)
            temp=dummy
            while left and right:
                if left.val<right.val:
                    temp.next=left
                    left=left.next
                else:
                    temp.next=right
                    right=right.next
                temp=temp.next
            temp.next= left if left else right
            return dummy.next
        if not head or not head.next:
            return head
        slow=head
        fast=head.next
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        mid=slow.next
        slow.next=None
        left=self.sortList(head)
        right=self.sortList(mid)
        return merge(left,right)