leetcode-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 = []
输出：[]

思路

使用快慢指针完成+合并两个有序链表完成归并排序

# Definition for singly-linked list.
class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = next
class Solution(object):def sortFunc(self, head, tail):if not head:return headif head.next == tail:head.next = Nonereturn headslow = fast = headwhile fast != tail:slow = slow.nextfast = fast.nextif fast != tail:fast = fast.nextmid = slowreturn self.merge(self.sortFunc(head, mid), self.sortFunc(mid, tail))def merge(self, head1, head2):pre = ListNode(-1)head, head1, head2 = pre, head1, head2while head1 and head2:if head1.val <= head2.val:head.next = head1head1 = head1.nextelse:head.next = head2head2 = head2.nexthead = head.nextif head1:head.next = head1if head2:head.next = head2return pre.nextdef sortList(self, head):""":type head: ListNode:rtype: ListNode"""return self.sortFunc(head, None)if __name__ == '__main__':s = Solution()head = ListNode(1)phead = headdata = [4, 3, 7, 5] for i in data:node = ListNode(i)phead.next = nodephead = phead.nexthead = s.sortList(head)while head:print(head.val),head = head.next