[알고리즘] Leetcode #147 삽입 정렬 리스트 (Python)

---

↓↓↓ 아래는 내 리트코드 & 깃허브 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

https://github.com/GodJiLee

GodJiLee - Overview

 

Leetcode #147 삽입 정렬 리스트

• 삽입정렬: 정답 셋의 가장 큰 값부터 왼쪽 방향으로 내려가며 스왑되는 위치를 찾음

# 삽입정렬 
cur = parent = ListNode(None)
while head:
    while cur.next and cur.next.val < head.val:
        cur = cur.next
        cur.next, head.next, head = head, cur.next, head.next
        
        cur = parent

# 전체 코드 
def insertionSortList(self, head):
    cur = parent = ListNode(None)
    while head:
        while cur.next and cur.next.val < head.val:
            cur = cur.next
        
        cur.next, head.next, head = head, cur.next, head.next
        cur = parent
    
    return cur.next

 

cur은 parent (None)으로 계속 고정시켜두고, head를 이동시키며 head와 cur.next의 값을 비교하여 정렬하는 과정을 반복한다.

• 1936 밀리초 소요 (타임아웃)

입력값이 연결리스트이기 때문에 큰 값에서부터 작은 값으로 크기비교하는 것이 불가능함

# 삽입 정렬의 비교 조건 개선
# 다음 while문에서의 head도 cur보다 크다면 cur = parent로 돌아가지 않도록

def insertionSortList(self, head):
    # 초깃값 변경
    cur = parent = ListNode(0)
    while head:
        while cur.next and cur.next.val < head.val:
            cur = cur.next
            
        cur.next, head.next, head = head, cur.next, head.next
        
        # 필요한 경우에만 cur 포인터가 되돌아가도록 처리
        if head and cur.val > head.val:
            cur = parent
    
    return parent.next

조건문을 추가하고 값 비교를 위해 cur와 parent의 초깃값을 ListNode(0)으로 초기화 (None으로 비교시 오류)

• 180 밀리초 소요 (최적화)