A Python solution


  • 0
    A
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    # 3 -> 2 -> 1
    # pr   c    n
    # q
    # 1 -> 3 -> 4
    class Solution:
        def insertionSortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head is None or head.next is None:
                return head
            curr = head.next
            prev = head
            p = None
            q = head
            while curr is not None:
                next = curr.next
                while q is not curr:
                    if q.val > curr.val:
                        if p is None:
                            head = curr
                        else:
                            p.next = curr
                        curr.next = q
                        prev.next = next
                        break
                    else:
                        p = q
                        q = q.next
                if q is curr:
                    prev = curr
                curr = next
                p = None
                q = head
            
            return head  
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.