LeetCode #147 Insertion Sort List

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #147 Insertion Sort List

문제 풀이

일반적인 삽입 정렬은 탐색 시작 지점부터 다음 지점과 대소관계를 비교해서 swap하는 과정으로 이루어지지만 ListNode는 클래스 변수로 val과 next밖에 않아 왼쪽 방향으로의 swap이 불가하다. 이를 해결하기 위해 별도의 ListNode를 저장할 객체를 선언하고 주어진 head의 각 노드에 대해 커서를 새로운 객체의 처음부터 마지막까지 탐색하여 조건이 충족되면 객체에 ListNode를 삽입하고 원점으로 돌아가 head의 다음 Node의 값과 비교연산을 수행하게 해야 한다.

python 코드

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        cur = node = ListNode(0)
        while head:
            while cur.next and cur.next.val < head.val:
                # cur.next의 값이 head보다 작아서 우측에 삽입할 필요가 없다면
                # cur 전진
                cur = cur.next
            # cur.next의 값이 head와 같거나 커서 우측에 삽입
            cur.next, head.next, head = head, cur.next, head.next
            if head and cur.val > head.val:
                # head가 존재하고 cur 값이 head보다 커서 좌측에 삽입해야 하면
                # cur를 원점으로 복귀
                cur = node
        return node.next