Insertion Sort List - LeetCode

문제 접근 🤔

💡 삽입 정렬 (insertion sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

• 입력으로 주어진 연결 리스트를 오름차순으로 정렬하는 문제
• 정렬된 연결 리스트를 저장할 빈 연결 리스트를 선언한다. 이를 dummy 라 하자.
• 입력으로 주어진 연결 리스트를 순회하면서, 각 노드마다 dummy에 삽입할 위치를 찾는다.
• 순회가 끝나면, dummy 는 정렬된 연결 리스트가 된다.
  
  
  

놓쳤던 부분 😅

• 처음에 반쪽짜리 정렬을 하게 되어서 찾아보니 빈 연결 리스트를 선언하여 추가해줘야 하는 문제였다. 🥹
  
  
  

코드 😁

파이썬 코드(64 ms)

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        dummy = curr = ListNode()
        while head:
            while curr.next and curr.next.val < head.val:
                curr = curr.next
            curr.next, head.next, head = head, curr.next, head.next
            if head and curr.val > head.val:
                curr = dummy
        return dummy.next