leetcode 148：排序链表(python)

忘是亡心i 2023-10-10 08:23 5阅读 0赞

# 题目 #

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3  
输出: 1->2->3->4  
示例 2:

输入: -1->5->3->4->0  
输出: -1->0->3->4->5

来源：力扣（LeetCode）  
链接：[LeetCode148. 排序链表][LeetCode148.]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 解法一（暴力法） #

*  思路  
    先把链表中的元素逐一取出，排序，在放入一个新链表内
 *  代码

# Definition for singly-linked list.
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution:
        def sortList(self, head: ListNode) -> ListNode:
            num=[]
            while head:
                num.append(head.val)
                head=head.next
            num.sort()
            myhead=ListNode(0)
            node=myhead
            while num:
                k=num.pop(0)
                node.next=ListNode(k)
                node=node.next
            return myhead.next

*  结果  
    ![在这里插入图片描述][20190928201806670.png]

# 解法二（归并排序法） #

*  思路  
    先折中归并排序，再合并两个有序链表
 *  代码

# Definition for singly-linked list.
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution:
        def sortList(self, head: ListNode) -> ListNode:
            if  not (head and head.next):
                return head
            p1,p2=head,head.next
            while p2 and p2.next:
                p1,p2=p1.next,p2.next.next
            head2,p1.next=p1.next,None
            list1=self.sortList(head)
            list2=self.sortList(head2)
            myhead=ListNode(0)
            node=myhead
            while list1 and list2:
                if list1.val>list2.val:
                    list1,list2=list2,list1
                node.next=list1
                node,list1=node.next,list1.next
            if list1:
                node.next=list1
            else: node.next=list2
            return myhead.next

*  结果  
    ![在这里插入图片描述][20190929220902784.png]

[LeetCode148.]: https://leetcode-cn.com/problems/sort-list
[20190928201806670.png]: https://img-blog.csdnimg.cn/20190928201806670.png
[20190929220902784.png]: https://img-blog.csdnimg.cn/20190929220902784.png