本文主要是介绍[LeetCode] 148. Sort List @ python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一．题目：
在时间复杂度O(n log n) 的情况下对链表排序．
二．解题思路：
很明显，这道题希望我们利用归并排序的方法对链表进行排序．所以首先我们需要找到链表的中点，可以用快慢指针；
寻找链表中点的代码如下：
#快慢指针寻找链表中点slow = head; fast = head while fast.next and fast.next.next:slow = slow.nextfast = fast.next.nexthead1 = headhead2 = slow.nextslow.next = None
然后，还需要设计一个合并两个排序链表的函数，代码如下：
def merge(self, head1, head2):if head1 == None: return head2if head2 == None: return head1dummy = ListNode(0) #归并时，新建一个链表头结点p = dummywhile head1 and head2:if head1.val <= head2.val:p.next = head1head1 = head1.nextp = p.nextelse:p.next = head2head2 = head2.nextp = p.nextif head1 == None:p.next = head2if head2 == None:p.next = head1return dummy.next
最终实现的代码如下所示：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution(object):def sortList(self, head):""":type head: ListNode:rtype: ListNode"""if head == None or head.next == None:return head#快慢指针技巧的运用，用来截断链表。head1和head2为截为两条链表的表头slow = head; fast = head while fast.next and fast.next.next:slow = slow.nextfast = fast.next.nexthead1 = headhead2 = slow.nextslow.next = None head1 = self.sortList(head1)head2 = self.sortList(head2)head = self.merge(head1, head2)return headdef merge(self, head1, head2):if head1 == None: return head2if head2 == None: return head1dummy = ListNode(0) #归并时，新建一个链表头结点p = dummywhile head1 and head2:if head1.val <= head2.val:p.next = head1head1 = head1.nextp = p.nextelse:p.next = head2head2 = head2.nextp = p.nextif head1 == None:p.next = head2if head2 == None:p.next = head1return dummy.next
这篇关于[LeetCode] 148. Sort List @ python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
