leetcode-147-对链表进行插入排序

# 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 not head or not head.next:
            return head
        
        dummy = ListNode(-1)
        dummy.next = head
        pre = head #pre始终指着排序好链表的最后一个节点
        cur = head.next #cur始终指着未排序链表的第一个节点
        while cur:
            tail = cur.next
            pre.next = tail  #把cur这个节点拿出来
            
            p = dummy
            while p.next and p.next.val < cur.val: #找到插入的位置
                p = p.next
                
            cur.next = p.next #把cur插入到p和p.next之间
            p.next = cur
            cur = tail
            
            if p == pre:#如果刚插入到了已排序链表的末尾
                pre = pre.next #那么就更新pre
        return dummy.next

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(float('-inf'))
        while head:
            p = dummy
            # 链表插排 找到最后一个比head小的节点指向head
            while p.next and p.next.val < head.val:
                p = p.next
            q = head # q替换head head往前走一步
            head = head.next
            p.next, q.next = q, p.next
        return dummy.next

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        #naive
        nodeList = []
        while(head):
            nodeList.append(head)
            head = head.next
        nodeList.sort(key=lambda x:x.val)
        dummy = ListNode(0)
        pre = dummy
        for node in nodeList:
            pre.next = node
            pre = node
        pre.next = None
        return dummy.next