Leetcode147-对链表进行插入排序(Python3实现)
2021-02-09 07:18
标签：大于 直接 lan pytho else get 无限循环 href solution 其实就是普通的插排，没想到中间还是因为尾节点的next指针没处理导致死循环，题目直接看链接，这里只是记录一下思路和代码。 解题思路： 需要注意的点： 1、增加一个极小值的头节点方便后面代码的撰写。 Leetcode147-对链表进行插入排序(Python3实现) 标签：大于 直接 lan pytho else get 无限循环 href solution 原文地址：https://www.cnblogs.com/lhdb/p/12751159.html
2、记录尾节点进行判断，减少总体循环的次数。
3、记得取出要判断的点时，尾节点的next要指向next.next节点，不然就无限循环了。# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if head==None:
return head
#在开头建一个无穷小节点，保证所有节点都大于该节点，方便后面代码撰写
res=ListNode(-float(‘inf‘))
res.next=head
now=head
cur=head.next
while cur:
#如果尾节点小于要判断的节点，则直接略过
if cur.val>=now.val:
cur,now=cur.next,cur
else:
pre=res
#将尾节点的next指向下一个要判断的节点
now.next=cur.next
#循环到左小右大的位置
while pre.next.valcur.val:
pre=pre.next
#将目标节点插入特定位置
tmp=pre.next
pre.next=cur
cur.next=tmp
#重新指向下一个要判断的节点，方便下一轮循环
cur=now.next
return res.next
文章标题：Leetcode147-对链表进行插入排序(Python3实现)
文章链接：http://soscw.com/index.php/essay/52996.html