LeetCode 147. Insertion Sort List

파이썬 알고리즘 인터뷰 60번(리트코드 147) Insertion Sort List
https://leetcode.com/problems/insertion-sort-list/

나의 풀이1

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        dummy = ListNode(-float("inf"))
        dummy.next = head
        last = head
        while last.next:
            if last.val <= last.next.val:
                last = last.next
            else:
                curr = last.next
                last.next = last.next.next
                before = dummy
                while before.next.val <= curr.val:
                    before = before.next
                curr.next, before.next = before.next, curr

        return dummy.next

나의 풀이2(개선)

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        dummy = ListNode(-float("inf"))
        dummy.next = head
        before = dummy
        last = head
        while last.next:
            if last.val <= last.next.val:
                last = last.next
            else:
                curr = last.next
                last.next = last.next.next
                if before.val > curr.val:
                    before = dummy
                while before.next.val <= curr.val:
                    before = before.next
                curr.next, before.next = before.next, curr

        return dummy.next

• 이번에 고른 curr를 어디에 넣을 지 탐색할 떄 항상 처음부터 탐색하지 않고, 이 전에 탐색한 곳을 먼저 살펴본 후, 적당하지 않으면 처음부터 탐색하도록 개선함.

다른 풀이1

# 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: Optional[ListNode]) -> Optional[ListNode]:
        cur = parent = ListNode(None)
        while head:
            while cur.next and cur.next.val < head.val:
                cur = cur.next
            cur.next, head.next, head = head, cur.next, head.next
            cur = parent
        return parent.next

• 나의 풀이와 같은 방식인데 가독성이 좋다.

다른 풀이2

# 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: Optional[ListNode]) -> Optional[ListNode]:
        cur = parent = ListNode(0)
        while head:
            while cur.next and cur.next.val < head.val:
                cur = cur.next
            cur.next, head.next, head = head, cur.next, head.next
            if head and cur.val > head.val:
                cur = parent
        return parent.next

• 나의 풀이1 → 2에서 개선한 것과 같은 방식으로 개선함.