<aside> 👉🏿 문제 링크

</aside>

문제 정리

<aside> 👉🏿 연결 리스트가 주어진다. 삽입 정렬을 사용하여 목록을 정렬하고 반환하라.

</aside>

Input: head = [4,2,1,3]
Output: [1,2,3,4]

접근 방법

<aside> 👉🏿 새로운 연결리스트를 생성한다.

주어진 연결 리스트에서 하나씩 꺼내 새로운 연결리스트에 넣는다.

</aside>

코드 진행

• 전체코드

<aside> 👉🏿 새로운 연결 리스트인 cur, parent를 생성한다.

</aside>

def insertionSortList(self, head):
    # cur과 parent 같은 연결리스트로 생성.
    # 추후 cur이 변경되었을 때 parent 리턴하기 위함.
    cur = parent = ListNode()

<aside> 👉🏿 head가 있을 경우 반복한다.

1. cur의 다음값이 head의 값보다 작을 경우 cur을 cur.next로 이동시킨다. </aside>

# cur의 다음값이 head의 값보다 작을 경우 cur을 다음 노드로 이동.
            while cur.next and cur.next.val < head.val:
                cur = cur.next

<aside> 👉🏿 다음과 같은 스와핑을 해준다.

</aside>