148. Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

My Answer 1: Time Limit Exceeded (25 / 28 test cases passed.)

# 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:
            return head
        
        result = ListNode(head.val)
        head = head.next
        resulthead = result
        resulttail = result
        
        while head:
            result = resulthead
            if head.val < result.val:       # 맨 앞에 추가
                newnode = ListNode(head.val)
                newnode.next = result
                result = newnode
                resulthead = result
            elif head.val > resulttail.val: # 맨 뒤에 추가
                resulttail.next = ListNode(head.val)
                resulttail = resulttail.next
            else:                           # 중간에 추가
                while result.next:
                    if head.val < result.next.val:
                        newnode = ListNode(head.val)
                        newnode.next = result.next
                        result.next = newnode
                        break
                    result = result.next
            head = head.next
        
        return resulthead

only 내 머리로 25/28 까지 달성했지만... 타임 리밋ㅠ

남은 3개 case 들은 무식하게 큰 놈들이다;

중간에 추가하는 부분에서 오래 걸리는 것 같아 resultmid 를 추가해주는 방식으로도 해봤지만 타임리밋은 고쳐지지 않음...

Solution 1: Runtime: 468 ms - 63.01% / Memory Usage: 30.2 MB - 35.27%

# 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 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

slow, fast 를 이용해서 merge 하는 건데 뭔소린지..

slow 가 중간값부터인건가...??