[LeetCode] 148 | Sort List | Python

---

문제 링크: https://leetcode.com/problems/sort-list/

---

문제

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

---

조건

• The number of nodes in the list is in the range [0, 5 * $10^4$].
• $-10^5$ <= Node.val <= $10^5$

---

내 풀이

1.

보통 이런 sorting문제에서 주로 사용되는 merge sort를 사용한다.

다만 list이기 때문에 반으로 나누는 함수(split)를 짜야하는데, 이는 fast와 slow를 이용해 절반이 되는 지점을 구한다.

합치는 함수(merge)는 간단하게 짤 수 있을 것이다.

 

2.

merge sort를 사용하지 않고, python의 내장 정렬 함수를 이용하면 간단하게 할 수도 있다.

list를 array로 바꾼 뒤에 정렬하고, 이를 다시 list로 만들어 출력한다.

---

코드

1. merge sort

# 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:    return head
        
        head2 = self.split(head)
        
        head1 = self.sortList(head)
        head2 = self.sortList(head2)
        
        return self.merge(head1, head2)
        
        
    def split(self, head):
        fast = slow = head
        prev = None
        
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        
        if prev: prev.next = None
        return slow
            
    
    def merge(self, first, second):
        merged1 = merged = ListNode()
        while first or second:
            val1 = first.val if first else 200000
            val2 = second.val if second else 200000
            
            if val1 < val2:
                merged.next = ListNode(val1)
                first = first.next
            else:
                merged.next = ListNode(val2)
                second = second.next
            merged = merged.next
            
        return merged1.next

 

2. 내장된 sorting 함수

# 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:    return head
        
        array = []
        while head.next:
            array.append(head.val)
            head = head.next
        array.append(head.val)
        
        array = sorted(array)
        ans = ListNode(array[0])
        ansC = ans
        for elem in array[1:]:
            ansC.next = ListNode(elem)
            ansC = ansC.next
        
        return ans