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

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

内容简介:首先要知道插入排序的过程,这个动态图看着挺清晰的插入排序动态图一共需要四个指针, 第一个:头指针,每一轮比较都是从头指针开始的,而且最后返回的也是头指针,所以头指针不能丢。 第二个:当前正在与前面做比较的指针,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》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

重新定义公司

重新定义公司

[美]埃里克·施密特 / 靳婷婷、陈序、何晔 / 中信出版社 / 2015-8 / 49.00

谷歌高管手绘风漫画视频: http://v.youku.com/v_show/id_XMTMxMzQ3NjMyMA==.html?from=y1.7-1.2 Google掌门人第一本国内引进作品 首次公开谷歌内部的管理与运营方法 全面解密执掌谷歌10余年的内幕故事 谷歌 创始人拉里•佩奇作序推荐 今日的谷歌是全球最具标志性的企业,在各个领域都有创新突破,并向技术......一起来看看 《重新定义公司》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

SHA 加密
SHA 加密

SHA 加密工具

html转js在线工具
html转js在线工具

html转js在线工具