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 = val
self.next = next
class Solution(object):
def sortFunc(self, head, tail):
if not head:
return head
if head.next == tail:
head.next = None
return head
slow = fast = head
while fast != tail:
slow = slow.next
fast = fast.next
if fast != tail:
fast = fast.next
mid = slow
return self.merge(self.sortFunc(head, mid), self.sortFunc(mid, tail))
def merge(self, head1, head2):
pre = ListNode(-1)
head, head1, head2 = pre, head1, head2
while head1 and head2:
if head1.val <= head2.val:
head.next = head1
head1 = head1.next
else:
head.next = head2
head2 = head2.next
head = head.next
if head1:
head.next = head1
if head2:
head.next = head2
return pre.next
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
return self.sortFunc(head, None)
if __name__ == '__main__':
s = Solution()
head = ListNode(1)
phead = head
data = [4, 3, 7, 5]
for i in data:
node = ListNode(i)
phead.next = node
phead = phead.next
head = s.sortList(head)
while head:
print(head.val),
head = head.next
原文地址:https://blog.csdn.net/m0_38098373/article/details/140702181
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!