[정렬] Leet code 147. Insertion Sort List

리트코드 문제 147
linked list로 주어지는 리스트를 삽입정렬을 이용해서 정렬하는 문제

풀이 1

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slist = ListNode()  # 더미
        slist.next = ListNode(head.val)
        head = head.next

        while head: # head가 끝나기 전까지
            p = slist
            new_node = ListNode(head.val) # 초기 세팅
            head = head.next
            while p.next: # p가 안끝난경우
                if p.next.val < new_node.val: # 경우 1
                    p = p.next
                else: # 경우 2
                    new_node.next = p.next
                    p.next = new_node
                    break
            if not p.next: # 경우 3 : p가 끝난경우 
                p.next = new_node

        return slist.next

• slist : 정렬해서 넣을 새로운 linked list
• 단방향이기 때문에 삽입할 곳의 바로 전 위치 찾기
• 첫번째일경우 아닐경우가 나뉘기 때문에 더미노드를 둬서 통일

풀이2

# 한줄로 쓰기
# p.next가 끝나던 p.next.val >= head.val이여서 자리를 찾던 넣어줘야한다 -> 합치기
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = slist = ListNode()

        while head:
            while p.next and p.next.val < head.val: # p값이 head값보다 작으면
                p = p.next

            p.next, head.next, head = head, p.next, head.next   # 중간에 삽입

            p = slist

        return slist.next

개선

• 한줄로 나타내서 삽입 코드 줄이기
• p가 끝나는 경우(경우3), 삽입 위치를 찾은 경우(경우2) 모두 new node를 뒤에 넣어줘야하기때문에 합치기

풀이3

#비교개선
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = slist = ListNode()

        while head:
            while p.next and p.next.val < head.val:  # p값이 head값보다 작으면
                p = p.next

            p.next, head.next, head = head, p.next, head.next

            if head and p.next.val > head.val: # 정렬한것중 최대값보다 작다면
                p = slist # 처음부터 비교

        return slist.next

• slist에서 가장 큰 값(p.next.val)보다 head.val이 크다면 처음부터 위치를 찾을필요없이 바로 삽입가능
• 따라서 p.next.val보다 head.val이 작을 때만 p를 처음으로 돌려서 다시 추적 -> 시간복잡도 획기적으로 줄임