+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-03(1)

2019-05(1)

2019-06(1)

2019-07(7)

2019-08(118)

python 排序链表

发布于2020-09-19 19:16     阅读(520)     评论(0)     点赞(7)     收藏(1)


0

1

2

3

4

5

6

  1. 题目描述:
  2. 在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
  3. 示例 1:
  4. 输入: 4->2->1->3
  5. 输出: 1->2->3->4
  6. 示例 2:
  7. 输入: -1->5->3->4->0
  8. 输出: -1->0->3->4->5
  1. class ListNode(object):
  2. '''定义创建链表节点的类'''
  3. def __init__(self, val, next = None):
  4. self.val = val
  5. self.next = next
  6. def sort_linked_list(head):
  7. # 分而治之,归并算法,涉及到链表排序的,可以考虑合并两个链表的方法
  8. # 合并两个链表
  9. def merge_two_linked_list(l1, l2):
  10. if not l1:
  11. return l2
  12. if not l2:
  13. return l1
  14. if l1.val < l2.val:
  15. cur = l1
  16. cur.next = merge_two_linked_list(l1.next, l2)
  17. else:
  18. cur = l2:
  19. cur.next = merge_two_linked_list(l1, l2.next)
  20. return cur
  21. if not head or not head.next:
  22. return head
  23. slow, fast = head, head.next
  24. while fast and fast.next:
  25. slow, fast = slow.next, fast.next.next
  26. mid, slow = slow.next, None
  27. left = sort_linked_list(head)
  28. right = sort_linked_list(mid)
  29. return merge_two_linked_list(left, right)

 

原文链接:https://blog.csdn.net/bang152101/article/details/108647578

0

1

2

3

4

5

6



所属网站分类: 技术文章 > 博客

作者:不上班你养我呀

链接: https://www.pythonheidong.com/blog/article/533064/a7ff4ecc11363a7edfd6/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

7 0
收藏该文
已收藏

评论内容:(最多支持255个字符)