148. 排序链表
Difficulty
Medium
Tags
链表
URL
https://leetcode.cn/problems/sort-list/
Star
法 1 归并排序
思路
常规归并排序方法。
题解
# 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 head is None or head.next is None: return head fst = head.next scd = head while fst and fst.next: fst = fst.next.next scd = scd.next l = head r = scd.next scd.next = None l = self.sortList(l) r = self.sortList(r) return self.merge(l, r) def merge(self, l1, l2): dummy = ListNode(-1) cur = dummy while l1 and l2: if l1.val < l2.val: cur.next = l1 l1 = l1.next cur = cur.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 if l1 else l2 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]: dummy1 = ListNode(-1, head) res = ListNode(-1) while dummy1.next: prev = dummy1 cur = dummy1.next max_prev = dummy1 while cur: if cur.val > max_prev.next.val: max_prev = prev prev = cur cur = cur.next max_node = max_prev.next max_prev.next = max_prev.next.next max_node.next = res.next res.next = max_node return res.next