greentea31's Note

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

풀이 과정

연결 리스트를 정렬하는 문제이다.

연결 리스트를 merge sort로 정렬해주거나, 연결 리스트를 리스트에 담고 내장 함수 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]:
        p = head
        lst = []
        
        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

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 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]:
        # head, head.next 둘다 null이면
        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)