LeetCode 148. Sort List

파이썬 알고리즘 인터뷰 58번(리트코드 148) Sort List
https://leetcode.com/problems/sort-list/

나의 풀이(Heap 이용 풀이)

# 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]:
        heap = []
        curr = head
        idx = 0

        while curr:
            heapq.heappush(heap, (curr.val, idx, curr))
            curr = curr.next
            idx += 1
        
        head = ListNode()
        curr = head

        while heap:
            curr.next = heapq.heappop(heap)[2]
            curr = curr.next
        curr.next = None
        return head.next

다른 풀이1(Merge Sort)

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        # Find the middle of the linked list 
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        mid = slow.next
        slow.next = None
        
        # Sort both halves
        left = self.sortList(head)
        right = self.sortList(mid)
        
        return self.merge(left, right)
    
    def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        tail = dummy
        
        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        
        tail.next = l1 if l1 else l2
        return dummy.next

다른 풀이2(배열로 바꾸기, 꼼수)

# 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]:
        
        curr = ans = head
        vals = []
        while curr:
            vals.append(curr.val)
            curr = curr.next
        
        vals.sort()

        for val in vals:
            ans.val = val
            ans = ans.next
        
        return head