[LeetCode] Sort-List (Python 풀이)

https://leetcode.com/problems/sort-list

 

• 말그대로 배열을 정렬하는 문제이다. 그런데 이제 배열이 링크드 리스트 자료구조로 만들어 져 있는 상태인 ! 
• 버블 소트같은거 밖에 생각못하다가 mergesort 로 풀어야 문제에서 조건으로 준 O(1) 공간 복잡도에 O(nlogn) 시간복잡도로 풀 수 있다. 
• 기본 merge sort 라면 공간 복잡도가 2n 이 되었겠지만, 여기서는 링크드리스트의 특성을 이용하여 O(1) 으로 풀 수 있다. (대박..)

 

LinkedList에서 중간 값(node) 를 구하는 로직이다. 낮은 값은 항상 한칸, 하나 더 큰 값은 항상 두칸씩 이동하다가 null 값을 만나면 순회를 멈추게 된다. 이렇게 하면서 중간값을 구하게 된다. LinkedList 문제에서 활용할 수 있을 것 같아 보인다 !!  

    # linkedlist에서 활용가능한 중앙값 구하는 함수 (대박)
    def get_mid(self, head):
        low, high = head, head.next 
        while high and high.next: 
            low = low.next 
            high = high.next.next
            
        return low

 

   merge sort에서 split 하는 로직을 실행하면 아래와 같이 나오게 된다. 

    4, 2, 1, 3
    [4, 2] [1, 3]
    [4] [2] [1] [3]

split 된 각각의 노드들을 merge 하면 아래와 같다.     

    left,  right 
    [2, 4] [1, 3]
    [1, 2, 3, 4]

이 과정에서  [2,4] [1, 3] 인 상태에서의 정렬을 예로 생각해 보자. 

• tail : ListNode()
• left : 2
• right : 1

left 가 현재 2, right 는 1 을 각각 가리킬 것이다. tail 은 더미 노드 현재 빈 상태이다. 
    
(2 > 1) 이므로 right 가 먼저 정렬되어야 한다. 

• 배열의 상태 : tail -> 1

right 가 가리키는 포인터를 한칸 이동시켜서 
right = right.next (3 을 가리킴)
현재는 3을 가리키게 한다. 

위의 과정을 계속해서 되풀이해준다. 

2와 3을 비교한다. (2 > 3) 그리고 left 가 가리키는 포인터를 한 칸 이동시킨다. 

left = left.next (4를 가리킴)

• 배열의 상태 : tail -> 1 -> 2 
• left : 3
• right : 4

3과 4를 비교한다. 

• 배열의 상태 : tail -> 1 -> 2 -> 3
• left : None
• right : 4

여전히 right 는 남아 있으므로 붙여준다. 

결과 : tail -> 1 -> 2 -> 3 -> 4 -> Null (dummy node 도 이어붙인다.)

전체 코드 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: # list 의 마지막 
            return head 
        
        # 두개의 리스트로 split 
        # split 을 위해 list 의 mid 값이 어디인지 구함. 
        left = head 
        right = self.get_mid(head)
        
        # right node 끝을 Null 값 처리함. 
        tmp = right.next
        right.next = None 
        right = tmp 
        
        left = self.sortList(left)
        right = self.sortList(right)
        return self.merge(left, right)
    
    # linkedlist에서 활용가능한 중앙값 구하는 함수 (대박)
    def get_mid(self, head):
        low, high = head, head.next 
        while high and high.next: 
            low = low.next 
            high = high.next.next
            
        return low 
    
              
    def merge(self, left, right):
        tail = dummy = ListNode()
        
        while left and right: 
            if left.val < right.val: 
                tail.next = left
                left = left.next 
            else: 
                tail.next = right
                right = right.next 
            tail = tail.next 
        # 남은 element 처리 
        if left: # not null 
            tail.next = left
        if right: 
            tail.next = right 
        return dummy.next 
        
# https://www.youtube.com/watch?v=TGveA1oFhrc
# 위의 풀이를 참고함..

 

https://www.youtube.com/watch?v=TGveA1oFhrc