리트코드 147번 Insertion Sort List (python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

삽입정렬을 이용하여 정렬해라

Solution

내 풀이

class Solution:
    def insert(self, val: int, sort_head: ListNode):
        if sort_head.next is None:
            sort_head.next = ListNode(val)
        else:
            prev, curr = sort_head, sort_head.next
            while curr and val >= curr.val:
                prev, curr = curr, curr.next

            prev.next = ListNode(val, curr)

    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        sort_head = ListNode()

        while head:
            self.insert(head.val, sort_head)
            head = head.next

        return sort_head.next

prev, curr을 하나씩 이동하다가 주어진 val이 prev ≤ val ≤ curr이 될 때 prev → val → curr으로 연결하였다

다른 풀이

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = parent = ListNode()
        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

계속 첫 노드부터 확인하는 내 풀이와 달리 필요할 때만 첫 노드로 이동함으로써 시간을 많이 줄인 풀이이다.

Reference

파이썬 알고리즘 인터뷰 60번