[Leetcode] 148. Sort List

문제 바로가기

Hash Table

Time Complexity: $O(n\log n)$
Space Complexity: $O(n)$

# 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: ListNode) -> ListNode:
        dic = dict()
        
        while head is not None:
            if head.val not in dic:
                dic[head.val] = []
            dic[head.val].append(head)
            head = head.next
        
        vals = sorted(list(dic.keys()))
        head = res = ListNode()
        # rearrange nodes in accending order
        for val in vals:
            for node in dic[val]:
                head.next = node
                head = head.next
        # remove cycle
        head.next = None

        return res.next

MergeSort

Recursion (Top down)

Time Complexity: $O(n\log n)$
Space Complexity: $O(\log n)$ - 함수 호출에 의한 stack

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        
        mid = self.divide(head)
        left = self.sortList(head)
        right = self.sortList(mid)
        return self.merge(left, right)
    
    def merge(self, left: ListNode, right: ListNode) -> ListNode:
        head = res = ListNode()
        while left is not None and right is not None:
            if left.val < right.val:
                head.next = left
                left = left.next
            else:
                head.next = right
                right = right.next
            head = head.next
        head.next = right if left is None else left
        return res.next
    
    def divide(self, head: ListNode) -> ListNode:
        # 원래는 slow의 위치가 mid인데, 단방향 연결 리스트여서 이전 노드로 돌아갈 수 없다.
        # left, right의 연결을 끊어야 하므로 시작점에 더미 노드를 추가해 한칸 늦춘다.
        slow = dummy = ListNode(0, head)
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        return mid

Iteration (Bottom up)

이론상 space complexity가 훨씬 작지만, 테스트케이스 실행 결과에서는 크게 체감되지 않았다.. 오히려 수행 시간이 20%정도(504mx -> 616ms) 길어졌다.

Time Complexity: $O(n\log n)$
Space Complexity: $O(1)$

# 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: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        
        n = self.getCount(head)
        size = 1
        start = head
        res = ListNode()
        while size < n:
            tail = res
            while start is not None:
                if start.next is None:
                    tail.next = start
                    break
                mid, nextSubList = self.split(start, size)
                tail = self.merge(start, mid, tail)
                start = nextSubList
            start = res.next
            size *= 2
        return res.next
    
    def split(self, head: ListNode, size: int) -> (ListNode, ListNode):
        # base case
        slow = head
        fast = head.next
        while size > 1 and slow.next:
            slow = slow.next
            if fast.next is not None:
                fast = fast.next.next if fast.next.next else fast.next
            size -= 1
        mid, nextSubList = slow.next, fast.next
        slow.next = fast.next = None
        return mid, nextSubList
    
    def merge(self, left: ListNode, right: ListNode, tail: ListNode) -> ListNode:
        head = res = ListNode()
        while left is not None and right is not None:
            if left.val < right.val:
                head.next = left
                left = left.next
            else:
                head.next = right
                right = right.next
            head = head.next
        head.next = right if left is None else left
        
        # tail update
        while head.next is not None:
            head = head.next
        tail.next = res.next
        return head # newTail
    
    def getCount(self, head: ListNode):
        count = 0
        while head is not None:
            count += 1
            head = head.next
        return count