BM12 单链表的排序

链接

单链表的排序_牛客题霸_牛客网 (nowcoder.com)

问题描述

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

数据范围: 0 < n≤100000
要求:空间复杂度O(n),时间复杂度0(nlogn)

示例1

输入: [1,3,2, 4,5]
返回值: {1,2,3,4,5}

示例2

输入: [-1,0,-2]
返回值: {-2,-1,0}

代码

这个是O(n²)的算法，选择排序

import random

# 链表的结点结构
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
# 传入一个数组，创建一个链表
def create_list(values):
    head = ListNode("head")
    current = head
    for value in values:
        node = ListNode(value)
        current.next = node
        current = node
    return head
# 输出一个链表
def print_list(head):
    current = head.next
    while current:
        print(current.val,end=" ")
        current = current.next
    print()

class Solution:
    # 链表排序
    def sortInList(self , head: ListNode) -> ListNode:
        # 1、设置新的头，设置一下当前指向的节点current
        new_head = ListNode("head")
        current = head.next
        # 2、current往后扫，摘掉一个接到newhead上
        while current:
            self.insert(new_head,current)
            current = current.next
        return new_head
    # 传入一个链表结点，插入到linkedlist中
    def insert(self,linkedlist,node):
        # 保存头结点和当前节点，包装一个newnode
        head = linkedlist
        current = head
        new_node = ListNode(node.val)
        # 往后找，找到比他大的
        if current.next is None:
            head.next = new_node
            return
        # 将节点插入到这个位置
        while current.next is not None and current.next.val < node.val:
            current = current.next
        new_node.next = current.next
        current.next = new_node



my_list = [random.randint(-100000,10000000) for i in range(100000)]
my_linklist = create_list(my_list)
# print_list(my_linklist)
s = Solution()
print_list(s.sortInList(my_linklist))

作弊的方法:O(nlogN)

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