147、对链表进行插入排序
题目：
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
插入排序 算法的步骤:
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
对链表进行插入排序
示例1：
输入: head = [4,2,1,3]
输出: [1,2,3,4]
示例2：
输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]
思路：
由于是插入排序，可以模拟数组插入排序，记录已排序序列的最后一个值，如果当前值小于这个值，说明需要将当前值插入到已排序序列中，那么从头开始比较，找到可以插入值的位置进行插入。
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
vHead = ListNode(0, head)
curSorted = head # 已排序的结点
cur = head.next # 当前遍历到的结点
while cur:
# 排序值小于当前值，说明当前是有序的，让排序值后移即可
if curSorted.val <= cur.val:
curSorted = curSorted.next
else:
# 遍历找到可以插入的位置
prev = vHead
while prev.next.val <= cur.val:
prev = prev.next
# 记录当前值的下一个指针，避免指针丢失
curSorted.next = cur.next
# 进行插入
cur.next = prev.next
prev.next = cur
# 将当前指针恢复到之前循环的位置
cur = curSorted.next
return vHead.next
148、排序链表
题目
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例3：
输入：head = []
输出：[]
思路
采用归并思想进行链表排序
class Solution:
# 找到链表中间
def getMedian(self, left, right):
slow = fast = left
while fast != right and fast.next != right:
fast = fast.next.next
slow = slow.next
return slow
# 合并链表
def merge(self, l1, l2):
cur = vHead = ListNode()
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return vHead.next
# 采用归并排序
def mergeSort(self, left, right):
if not left: return left
# 如果左节点的下一个节点指向右节点，说明当前只有一个结点，可以将后续结点置空，返回进行排序
if left.next == right:
left.next = None
return left
mid = self.getMedian(left, right)
return self.merge(self.mergeSort(left, mid), self.mergeSort(mid, right))
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head: return head
return self.mergeSort(head, None)
网友评论