我要招人

去企业版

首页 > 试题广场 >

单链表的排序

[编程题]单链表的排序

热度指数：131240 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个节点数为n的无序单链表，对其按升序排序。

数据范围： $0 < n \le 100000$ ，保证节点权值在 $[-10^9,10^9]$ 之内。

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

示例1

输入

[1,3,2,4,5]

输出

{1,2,3,4,5}

示例2

输入

[-1,0,-2]

输出

{-2,-1,0}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Python3

喜欢吃火锅的杰尼龟快支棱起来

Python3 归并排序，感谢GPT教我刷题

class Solution:
    def sortInList(self, head: ListNode) -> ListNode:
        if not head&nbs***bsp;not head.next:
            return head  # 如果是基本情况（单个节点或空列表），则返回当前节点

        # 寻找中点
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        mid = slow.next
        slow.next = None

        left = self.sortInList(head)
        right = self.sortInList(mid)

        # 合并排序后的列表
        dummy = ListNode(0)
        cur = dummy
        while left and right:
            if left.val < right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        cur.next = left&nbs***bsp;right

        return dummy.next

发表于 2024-04-10 09:28:48 回复(0)

Python3

kuangk

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 the head node
# @return ListNode类
#
class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        # write code here
        if head is None:
            return None
        s = []
        while head :
                s.append(head.val)
                head = head.next
        s = sorted(s)
        res = ListNode(0)
        temp = res
        for i in s :
            temp.next = ListNode(i)
            temp = temp.next
        return res.next

发表于 2024-03-05 08:32:09 回复(0)

Python3

牛客429226965号

报意思，快排没过，有没有大佬能帮忙看看咋优化呀~~

class Solution:
    def sortInList(self , head: ListNode):
        # write code here
        def quickSort(head) -> ListNode:
            if head == None&nbs***bsp;head.next == None:
                return head
            index = head.val
            lNode = None
            rNode = None
            mNode = None
            p = head
            # 插在头节点处
            while p != None:
                temp = ListNode(p.val)
                if p.val == index:
                    temp.next = mNode
                    mNode = temp
                elif p.val > index:
                    temp.next = rNode
                    rNode = temp
                else:
                    temp.next = lNode
                    lNode = temp
                p = p.next

            # 返回了头节点，且有可能为None
            l1 = quickSort(lNode) 
            l2 = getTail(mNode)
            l2.next = quickSort(rNode)
            if l1 == None:
                return mNode
            else:
                l1Tail = getTail(l1)
                l1Tail.next = mNode
                return l1
                
        def getTail(head):
            if head == None:
                return None
            while head.next != None:
                head = head.next
            return head
        return quickSort(head)

发表于 2023-08-17 14:23:01 回复(1)

Python3

Honey、

class Solution:

def sortInList(self , head: ListNode) -> ListNode:

# write code here

num = []

while head:

num.append(head.val)

head = head.next

numed = sorted(num)

new = ListNode(-1)

cur = new

for i in numed:

cur.next = ListNode(i)

cur = cur.next

return new.next

发表于 2023-06-08 14:45:13 回复(0)

Python3

牛客606997114号

class Solution:
def sortInList(self , head ):
# write code here
list1=[]
cur = head
while(cur):
list1.append(cur.val)
cur=cur.next
cur = head
for i in sorted(list1):
cur.val=i
cur=cur.next
return head

发表于 2022-03-11 12:43:45 回复(0)

Python3

牛客343459580号

# @param head ListNode类 the head node
# @return ListNode类
#
class Solution:
    def sortInList(self , head ):
        # write code here
        list1 = []
        while(head):
            list1.append(head.val)
            head = head.next
        list1.sort()
        temp = ListNode(0)
        pHead = temp
        for i in list1:
            pHead.next = ListNode(i)
            pHead = pHead.next
        return temp.next

发表于 2021-09-03 20:46:42 回复(2)