[코테] 리트코드 정렬 148. Sort List

148. Sort List

문제 링크

https://leetcode.com/problems/sort-list/description/

문제 설명

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

1. Input : head = [4,2,1,3]
2. Output : [1,2,3,4]

입출력 예 #2

1. Input : head = [-1,5,3,4,0]
2. Output : [-1,0,3,4,5]

입출력 예 #3

1. Input : head = []
2. Output : []

문제 풀이

1. 병합 정렬을 이용한 풀이
2. 연결 리스트를 파이썬 리스트로 변환 이후 내장 함수를 이용한 풀이

class Solution:
    # 두 정렬 리스트 병합
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val:
                l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2)

        return l1 or l2

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not (head and head.next):
            return head

        # 런너 기법 활용
        half, slow, fast = None, head, head
        while fast and fast.next:
            half, slow, fast = slow, slow.next, fast.next.next
        half.next = None

        # 분할 재귀 호출
        l1 = self.sortList(head)
        l2 = self.sortList(slow)

        return self.mergeTwoLists(l1, l2)

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 연결 리스트 -> 파이썬 리스트
        p = head
        lst = List = []
        while p:
            lst.append(p.val)
            p = p.next

        # 정렬
        lst.sort()

        # 파이썬 리스트 -> 연결 리스트
        p = head
        for i in range(len(lst)):
            p.val = lst[i]
            p = p.next
        return head