每日一道算法题--leetcode 147--对链表进行插入排序--python

栏目: Python · 发布时间: 6年前

内容简介:首先要知道插入排序的过程,这个动态图看着挺清晰的插入排序动态图一共需要四个指针, 第一个:头指针,每一轮比较都是从头指针开始的,而且最后返回的也是头指针,所以头指针不能丢。 第二个:当前正在与前面做比较的指针,p。 第三个:由于p与前面已经排好顺序的链表比较完之后,p.next就会丢失了,所以要先保存起来,pnext=p.next. 第四个:与前面链表比较时,移动的指针q,q从头指针开始,在循环中向后移动。把p之前的链表与p之间断开,不然在q向后移动的时候会到整个大链表的结尾处,

【题目描述】

每日一道算法题--leetcode 147--对链表进行插入排序--python
【代码思路】

首先要知道插入 排序 的过程,这个动态图看着挺清晰的插入排序动态图

一共需要四个指针, 第一个:头指针,每一轮比较都是从头指针开始的,而且最后返回的也是头指针,所以头指针不能丢。 第二个:当前正在与前面做比较的指针,p。 第三个:由于p与前面已经排好顺序的链表比较完之后,p.next就会丢失了,所以要先保存起来,pnext=p.next. 第四个:与前面链表比较时,移动的指针q,q从头指针开始,在循环中向后移动。

把p之前的链表与p之间断开,不然在q向后移动的时候会到整个大链表的结尾处,

head.next=None
复制代码

如果当前指针比头指针还要小,那么头指针就要改变成当前指针,当前指针指向原来的头指针。

if p.val<q.val:
    p.next=q
     head=p
复制代码

如果当前指针比头指针大,就可以用q来在循环中向后移动,对比的是q.next和p的值,

while q is not None and q.next is not None and p.val>=q.val:
    q=q.next
复制代码

这样的话,当q.next比p值小额时候,q就向后移动;当检测到比p.val大的值的时候,指针q还在比他大的那个位置之前,就可以直接用

p.next=q.next
q.next=p
复制代码

【源代码】

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        if head is None or head.next is None:return head
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p=head.next
        head.next=None
        while  p is not None:
            q=head
            pnext=p.next
            if p.val<q.val:
                p.next=q
                head=p
            else:
                while q is not None and q.next is not None and p.val>=q.val:
                    q=q.next
                p.next=q.next 
                q.next=p
            p=pnext
        return head
复制代码

以上所述就是小编给大家介绍的《每日一道算法题--leetcode 147--对链表进行插入排序--python》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Python语言程序设计基础(第2版)

Python语言程序设计基础(第2版)

嵩天、礼欣、黄天羽 / 高等教育出版社 / 2017-2 / 39

本书提出了以理解和运用计算生态为目标的Python语言教学思想,不仅系统讲解了Python语言语法,同时介绍了从数据理解到图像处理的14个Python函数库,向初学Python语言的读者展示了全新的编程语言学习路径。 全书一共设计了25个非常具有现代感的实例,从绘制蟒蛇、理解天天向上的力量到机器学习、网络爬虫,从文本进度条、统计名著人物重要性到图像手绘效果、雷达图绘制,绝大多数实例为作者原创......一起来看看 《Python语言程序设计基础(第2版)》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换