linked list 정렬하기

 

linked list를 정렬하는데 추가적인 메모리를 쓰지 않고 O(nlogn)의 시간복잡도로 하기 위해선 어떻게 해야할까?

답은 merge sort를 쓰면 된다!!!!

 

그런데 조금 복잡한 부분이 일반적인 array의 경우 index로 분할하여 정렬하면 되는데 linked list의 경우 어떻게 나누어야 하는지이다. 이를 위해선 3개의 포인터를 쓰면 된다. 그 세 포인터를 각각 p,slow,fast라 해보자. p,slow,fast가 차례로 한 칸씩 전진하는데 p->slow->fast의 순서대로 나아간다. 이 때, fast가 None이거나 fast.next가 None이 되면 p.next를 None으로 만들어주고 p와 slow로 linked list를 분할한다. 그럼 p가 가리키는 연결리스트가 l이 되고, slow가 가리키는 연결리스트가 r이 된다. 그리고 이 둘을 merge하는 과정을 반복한 뒤 둘을 이어주면 된다. 

만약, -1->5->3->4->0을 정렬한다고 해보자. 분할의 과정을 그림으로 나타내보면 아래와 같다.

 

관련 문제

---

leetcode.com/problems/sort-list/

Sort List - LeetCode

 

코드

---

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        p, slow, fast = None, head, head
        while fast and fast.next:
            p = slow
            slow = slow.next
            fast = fast.next.next
        p.next = None
        
        return self.merge(self.sortList(head), self.sortList(slow))
    
    def merge(self, l1, l2):
        dummy = ListNode(None)
        curr = dummy
        
        while l1 and l2:
            if l1.val > l2.val:
                curr.next, l2 = l2, l2.next
            else:
                curr.next, l1 = l1, l1.next
            curr = curr.next
        
        if l1:
            curr.next = l1
        elif l2:
            curr.next = l2
        
        return dummy.next