LeetCode147.对链表进行插入排序(Python)
2022/1/6 17:05:24
本文主要是介绍LeetCode147.对链表进行插入排序(Python),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目思路:
可以理解为利用两个指针,一个对整个链表进行遍历,另一个在已经遍历过的线段寻找插入点。(建议画图便于理解)
利用
class Solution: def insertionSortList(self, head: ListNode) -> ListNode: # 首先判断链表是否为空 if not head: return head # 令dummy.head指向head,创建哑节点是为了方便将值插入头节点之前。 dummyhead = ListNode(0) dummyhead.next = head # lastsorted可以看成已经排序了的列表 lastsorted = head cur = head.next while cur: if lastsorted.val <= cur.val: lastsorted = lastsorted.next else: pre = dummyhead # 寻找cur值应该插入的点 while pre.next.val <= cur.val: pre = pre.next lastsorted.next = cur.next cur.next = pre.next pre.next = cur # 继续遍历下一个点 cur = lastsorted.next return dummyhead.next
时间复杂度:
这篇关于LeetCode147.对链表进行插入排序(Python)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python