PeterQwQ
0%

Leetcode 148 排序链表

发表于

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

创建一个字典，将链表节点和节点值对应起来，然后对字典进行排序，最后根据排序后的字典创建新的链表，返回即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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
        dic = {}
        cur = head
        while cur:
            dic[cur] = cur.val
            cur = cur.next
        sorted_dic = sorted(dic.items(), key=lambda x: x[1])
        
        new_head = ListNode(sorted_dic[0][1])
        cur = new_head
        for i in range(1, len(sorted_dic)):
            cur.next = ListNode(sorted_dic[i][1])
            cur = cur.next
        return new_head