<reponame>KuiyuanFu/PythonLeetCode
# @lc app=leetcode id=147 lang=python3
#
# [147] Insertion Sort List
#
# https://leetcode.com/problems/insertion-sort-list/description/
#
# algorithms
# Medium (44.99%)
# Likes:    1100
# Dislikes: 691
# Total Accepted:    233.4K
# Total Submissions: 518.3K
# Testcase Example:  '[4,2,1,3]'
#
# Given the head of a singly linked list, sort the list using insertion sort,
# and return the sorted list's head.
#
# The steps of the insertion sort algorithm:
#
#
# Insertion sort iterates, consuming one input element each repetition and
# growing a sorted output list.
# At each iteration, insertion sort removes one element from the input data,
# finds the location it belongs within the sorted list and inserts it
# there.
# It repeats until no input elements remain.
#
#
# The following is a graphical example of the insertion sort algorithm. The
# partially sorted list (black) initially contains only the first element in
# the list. One element (red) is removed from the input data and inserted
# in-place into the sorted list with each iteration.
#
#
# Example 1:
#
#
# Input: head = [4,2,1,3]
# Output: [1,2,3,4]
#
#
# Example 2:
#
#
# Input: head = [-1,5,3,4,0]
# Output: [-1,0,3,4,5]
#
#
#
# Constraints:
#
#
# The number of nodes in the list is in the range [1, 5000].
# -5000 <= Node.val <= 5000
#
#
#

# @lc tags=linked-list;sort

# @lc imports=start
from imports import *

# @lc imports=end

# @lc idea=start
#
# 链表的插入排序。
# 直接使用最朴素的思想。
#
# @lc idea=end

# @lc group=

# @lc rank=


# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:

        pseudo = ListNode()
        p = head
        while p:
            pN = p.next
            r = pseudo
            while r.next:
                if r.next.val < p.val:
                    r = r.next
                else:
                    break
            p.next = r.next
            r.next = p
            p = pN
        return pseudo.next
        pass


# @lc code=end

# @lc main=start
if __name__ == '__main__':
    print('Example 1:')
    print('Input : ')
    print('head = [4,2,1,3]')
    print('Exception :')
    print('[1,2,3,4]')
    print('Output :')
    print(str(Solution().insertionSortList(listToListNode([4, 2, 1, 3]))))
    print()

    print('Example 2:')
    print('Input : ')
    print('head = [-1,5,3,4,0]')
    print('Exception :')
    print('[-1,0,3,4,5]')
    print('Output :')
    print(str(Solution().insertionSortList(listToListNode([-1, 5, 3, 4, 0]))))
    print()

    pass
# @lc main=end
# @lc app=leetcode id=147 lang=python3
#
# [147] Insertion Sort List
#
# https://leetcode.com/problems/insertion-sort-list/description/
#
# algorithms
# Medium (44.99%)
# Likes:    1100
# Dislikes: 691
# Total Accepted:    233.4K
# Total Submissions: 518.3K
# Testcase Example:  '[4,2,1,3]'
#
# Given the head of a singly linked list, sort the list using insertion sort,
# and return the sorted list's head.
#
# The steps of the insertion sort algorithm:
#
#
# Insertion sort iterates, consuming one input element each repetition and
# growing a sorted output list.
# At each iteration, insertion sort removes one element from the input data,
# finds the location it belongs within the sorted list and inserts it
# there.
# It repeats until no input elements remain.
#
#
# The following is a graphical example of the insertion sort algorithm. The
# partially sorted list (black) initially contains only the first element in
# the list. One element (red) is removed from the input data and inserted
# in-place into the sorted list with each iteration.
#
#
# Example 1:
#
#
# Input: head = [4,2,1,3]
# Output: [1,2,3,4]
#
#
# Example 2:
#
#
# Input: head = [-1,5,3,4,0]
# Output: [-1,0,3,4,5]
#
#
#
# Constraints:
#
#
# The number of nodes in the list is in the range [1, 5000].
# -5000 <= Node.val <= 5000
#
#
#

# @lc tags=linked-list;sort

# @lc imports=start
from imports import *

# @lc imports=end

# @lc idea=start
#
# 链表的插入排序。
# 直接使用最朴素的思想。
#
# @lc idea=end

# @lc group=

# @lc rank=


# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:

        pseudo = ListNode()
        p = head
        while p:
            pN = p.next
            r = pseudo
            while r.next:
                if r.next.val < p.val:
                    r = r.next
                else:
                    break
            p.next = r.next
            r.next = p
            p = pN
        return pseudo.next
        pass


# @lc code=end

# @lc main=start
if __name__ == '__main__':
    print('Example 1:')
    print('Input : ')
    print('head = [4,2,1,3]')
    print('Exception :')
    print('[1,2,3,4]')
    print('Output :')
    print(str(Solution().insertionSortList(listToListNode([4, 2, 1, 3]))))
    print()

    print('Example 2:')
    print('Input : ')
    print('head = [-1,5,3,4,0]')
    print('Exception :')
    print('[-1,0,3,4,5]')
    print('Output :')
    print(str(Solution().insertionSortList(listToListNode([-1, 5, 3, 4, 0]))))
    print()

    pass
# @lc main=end
# @lc app=leetcode id=147 lang=python3 # # [147] Insertion Sort List # # https://leetcode.com/problems/insertion-sort-list/description/ # # algorithms # Medium (44.99%) # Likes:    1100 # Dislikes: 691 # Total Accepted:    233.4K # Total Submissions: 518.3K # Testcase Example:  '[4,2,1,3]' # # Given the head of a singly linked list, sort the list using insertion sort, # and return the sorted list's head. # # The steps of the insertion sort algorithm: # # # Insertion sort iterates, consuming one input element each repetition and # growing a sorted output list. # At each iteration, insertion sort removes one element from the input data, # finds the location it belongs within the sorted list and inserts it # there. # It repeats until no input elements remain. # # # The following is a graphical example of the insertion sort algorithm. The # partially sorted list (black) initially contains only the first element in # the list. One element (red) is removed from the input data and inserted # in-place into the sorted list with each iteration. # # # Example 1: # # # Input: head = [4,2,1,3] # Output: [1,2,3,4] # # # Example 2: # # # Input: head = [-1,5,3,4,0] # Output: [-1,0,3,4,5] # # # # Constraints: # # # The number of nodes in the list is in the range [1, 5000]. # -5000 <= Node.val <= 5000 # # # # @lc tags=linked-list;sort # @lc imports=start # @lc imports=end # @lc idea=start # # 链表的插入排序。 # 直接使用最朴素的思想。 # # @lc idea=end # @lc group= # @lc rank= # @lc code=start # Definition for singly-linked list. # class ListNode: #     def __init__(self, val=0, next=None): #         self.val = val #         self.next = next # @lc code=end # @lc main=start # @lc main=end