148. Sort List

148. Sort List

 

https://youtu.be/TGveA1oFhrc?si=rRYsC927YCXjnEcg

 

# 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]:
        # time: n log n => merge sort
        # memory: O(1) => can Recursion, 재귀
        if not head or not head.next:
            return head  # 리스트가 비어 있거나, 노드가 하나뿐이라면 이미 정렬된 상태이므로 반환

        # split the list into two halves
        left = head  # 왼쪽 절반의 시작은 head
        mid = self.getMid(head)  # 리스트 중간 노드 찾기
        right = mid.next  # 중간 다음 노드는 오른쪽 리스트의 시작

        # 연결 리스트를 정확히 두 개로 나누지 않으면, 
        # 재귀 호출 및 병합 과정에서 오류가 발생
        # 따라서 리스트를 올바르게 분할하기 위해 꼭 필요
        mid.next = None  # 중간 노드의 다음 링크를 끊어서 두 리스트로 분리

        # 왼쪽 리스트와 오른쪽 리스트를 재귀적으로 정렬
        left = self.sortList(left)
        right = self.sortList(right)

        # 정렬된 두 리스트를 병합하여 결과 반환
        return self.merge(left, right)

    def getMid(self, head):
        # 중간 노드를 찾기 위해 두 포인터 사용
        # slow: 한 번에 한 칸씩 이동
        # fast: 한 번에 두 칸씩 이동
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next  # slow는 한 칸 이동
            fast = fast.next.next  # fast는 두 칸 이동
        return slow  # slow가 중간 노드를 가리킴

    def merge(self, list1, list2):
        # 두 개의 정렬된 리스트를 병합하는 함수
        tail = dummy = ListNode()  # 병합 결과를 저장할 더미 노드 생성

        # 두 리스트를 비교하면서 작은 값을 결과 리스트에 추가
        while list1 and list2:
            if list1.val < list2.val:  # list1의 값이 작을 경우
                tail.next = list1  # list1의 현재 노드를 결과 리스트에 추가
                list1 = list1.next  # list1의 다음 노드로 이동
            else:  # list2의 값이 작거나 같을 경우
                tail.next = list2  # list2의 현재 노드를 결과 리스트에 추가
                list2 = list2.next  # list2의 다음 노드로 이동
            tail = tail.next  # 결과 리스트의 마지막 노드 갱신

        # list1 또는 list2에 남아 있는 노드를 결과 리스트에 연결
        if list1:
            tail.next = list1
        if list2:
            tail.next = list2

        return dummy.next  # 더미 노드의 다음 노드가 병합된 결과의 시작점

 

추가된 상세 주석 설명

1. if not head or not head.next: 조건:
   • 리스트가 비어 있거나 노드가 하나뿐인 경우 이미 정렬된 상태이므로 그대로 반환.
2. mid.next = None:
   • 연결 리스트를 정확히 두 개로 나누기 위해 중간 노드의 다음 링크를 끊습니다.
3. getMid 함수:
   • 두 포인터(slow와 fast)를 사용해 리스트의 중간 노드를 효율적으로 찾습니다.
   • fast가 끝에 도달할 때 slow는 중간에 위치합니다.
4. merge 함수:
   • 두 개의 정렬된 리스트를 병합합니다.
   • 더미 노드(dummy)를 사용해 병합된 결과를 쉽게 연결합니다.