每日一道算法题--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
复制代码