Sort List

+10

같은 길이의 두 배열에 저장된 단일 연결 리스트가 주어집니다. 노드 i는 값 values[i]를 가지며 노드 next[i]에 연결됩니다. -1은 리스트의 끝을 나타내고, 헤드는 노드 0입니다. 노드들은 리스트 순서대로 저장되어 있지 않으며, 배열에는 노드 0에서 따라가도 도달할 수 없는 남은 노드가 들어 있을 수도 있습니다. 이 노드들은 연결이 리스트 내부를 가리키더라도 리스트에 포함되지 않습니다.

값의 비내림차순으로 리스트를 정렬하고, 그 순서대로 노드의 값들을 반환하세요.

함수

sortList(next: integer-array, values: integer-array) → integer-array

nextinteger-array: 각 노드가 연결하는 노드의 인덱스 또는 마지막 노드의 경우 -1
valuesinteger-array: 각 노드가 보유한 값
반환값integer-array: 리스트 노드의 값, 가장 작은 값부터

제약 조건

1 ≤ n ≤ 4000이며, 여기서 n은 next와 values의 길이입니다.
-1000 ≤ values[i] ≤ 1000
각 next[i]는 -1이거나 0부터 n-1까지의 노드 인덱스입니다.
노드 0에서 시작해, 목록은 노드를 두 번 방문하지 않고 -1에 도달합니다.
노드 0에서 시작하는 순회가 도달하지 못하는 노드들은 목록의 일부가 아닙니다. 해당 노드들의 next 항목은 어디든 가리킬 수 있습니다.

예제

입력: next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
출력: [1, 2, 3, 4, 5]
설명: 노드 0에서 시작하는 순회는 노드 0, 3, 2, 4, 1을 방문하므로, 리스트는 4, 2, 3, 5, 1입니다. 정렬하면 1, 2, 3, 4, 5입니다.

입력: next = [2, 0, -1, -1]values = [6, 9, -2, 5]
출력: [-2, 6]
설명: 목록은 0 → 2이며, 값은 6, -2입니다. 노드 1과 3은 헤드에서 도달할 수 없으므로, 노드 1이 노드 0에 연결되어 있더라도 해당 값인 9와 5는 제외됩니다.

입력: next = [1, 2, 3, -1]values = [3, -1, 3, -1]
출력: [-1, -1, 3, 3]
설명: 목록에는 3, -1, 3, -1이 있습니다. 같은 값은 나타나는 횟수만큼 답에 포함됩니다: -1, -1, 3, 3.

후속 질문

값을 복사하지 않고 O(n log n) 시간에 노드를 다시 연결하여 정렬할 수 있나요?

풀이

퀵 정렬과 힙 정렬은 임의 접근에 의존하지만, 단일 연결 리스트는 앞으로만 이동합니다. 병합 정렬이 적합합니다. 리스트를 중간에서 나누고 정렬된 두 리스트를 병합하는 작업은 모두 앞으로 이동하므로, 링크 자체를 O(n log n)에 정렬합니다. 여기서 n은 배열의 길이입니다.

값을 배열에 복사하고 정렬하세요

핵심 아이디어

목록은 node = next[node]를 따라가며 노드 0에서 -1에 도달할 때까지 방문하는 값들입니다. 그 값을 새 배열에 모아 내장 정렬 기능으로 정렬한 다음 반환하세요. values를 직접 정렬하면 안 됩니다. 두 번째 예시에서 values에는 목록에 없는 9와 5가 들어 있기 때문입니다.

순회에는 O(n), 정렬에는 O(n log n)이 걸리며, 추가 메모리는 O(n)입니다. 목록 자체는 전혀 건드리지 않으므로 면접관은 다음 접근 방식을 묻습니다.

알고리즘

빈 배열로 시작하고 node = 0으로 설정합니다.
node가 -1이 아닌 동안 values[node]를 추가하고 next[node]로 이동합니다.
배열을 오름차순으로 정렬하고 반환합니다.

def sortList(next, values):
    # Collect the values of the nodes on the list, then sort them.
    on_list = []
    node = 0
    while node != -1:
        on_list.append(values[node])
        node = next[node]
    on_list.sort()
    return on_list

링크에 대한 병합 정렬

핵심 아이디어

한 칸씩 이동하는 느린 포인터와 두 칸씩 이동하는 빠른 포인터를 사용하면 한 번 순회하는 동안 중간을 찾을 수 있습니다. 정렬된 두 연결 리스트를 병합할 때는 각 리스트의 맨 앞 노드만 확인하면 됩니다. 더 작은 노드를 가져온 다음 그 노드 너머로 이동하세요. 두 과정 모두 두 번째 배열이 필요하지 않습니다.

첫 번째 예제에서 slow는 3에서 멈추고, 이 노드의 링크를 끊으면 4, 2, 3, 5, 1이 4, 2, 3과 5, 1로 나뉩니다. 이를 정렬하면 2, 3, 4와 1, 5가 되고, 병합할 때 1, 2, 3, 4를 차례로 가져온 다음 남은 5를 연결합니다.

분할의 각 단계에서는 모든 노드를 상수 횟수만큼 방문하며, 단계는 약 log n개이므로 시간 복잡도는 O(n log n)입니다. 추가 메모리는 재귀 호출 스택뿐이며, 노드가 4000개일 때 호출 깊이는 약 12입니다.

알고리즘

리스트에 노드가 하나 있으면 (next[head] == -1) head를 반환합니다.
slow = head와 fast = next[head]로 시작합니다. fast와 next[fast]가 -1이 아닐 동안 slow는 링크 하나, fast는 링크 두 개씩 이동합니다.
second = next[slow]로 지정하고 next[slow] = -1로 잘라냅니다.
두 부분을 재귀적으로 정렬합니다. 병합할 때는 한쪽 부분이 빌 때까지 더 작은 앞쪽 노드를 tail 뒤에 연결한 다음, 다른 쪽의 나머지를 연결합니다.
반환된 헤드부터 순회하며 값을 수집합니다.

def sortList(next, values):
    def merge(a, b):
        # Splice two sorted lists into one; on a tie the node from a goes first.
        head = tail = -1
        while a != -1 and b != -1:
            if values[b] < values[a]:
                node, b = b, next[b]
            else:
                node, a = a, next[a]
            if tail == -1:
                head = node
            else:
                next[tail] = node
            tail = node
        next[tail] = a if a != -1 else b  # attach whatever is left
        return head

    def sort(head):
        if next[head] == -1:  # one node is already sorted
            return head
        # slow stops on the last node of the first half
        slow, fast = head, next[head]
        while fast != -1 and next[fast] != -1:
            slow = next[slow]
            fast = next[next[fast]]
        second = next[slow]
        next[slow] = -1  # cut the list in two
        return merge(sort(head), sort(second))

    result = []
    node = sort(0)
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

함정과 경계 사례

전체 values 배열을 정렬하는 것. 두 번째 예제에서는 목록에 없는 9와 5가 포함됩니다.
머리에서 fast를 시작하는 것. 노드가 두 개일 때 slow는 두 번째 노드에 도달하고, 분할하면 두 번째 절반이 비어 재귀 호출의 입력 크기가 줄어들지 않습니다.
분할을 위한 next[slow] = -1을 빠뜨리는 것. 그러면 첫 번째 절반이 두 번째 절반까지 이어져, 두 호출이 서로 겹치는 목록을 정렬합니다.
다른 쪽이 먼저 끝났을 때 한쪽 절반의 나머지를 버리는 것. 그 노드들이 결과에서 사라집니다.
Lua와 R에서는 배열이 1부터 시작합니다. 노드 인덱스는 0부터 시작하도록 유지하고 next[node + 1]을 읽으세요. R 버전은 링크 배열을 한 번 복사하므로 O(n)의 추가 메모리를 사용합니다.

자주 묻는 질문3

연결 리스트를 정렬하는 가장 좋은 방법은 무엇인가요?

병합 정렬입니다. 중간에서 나누고 양쪽 절반을 정렬한 다음 병합하는 과정은 모두 목록을 앞으로 따라갑니다. 단일 연결 리스트가 지원하는 방향은 이것뿐입니다. 실행 시간은 O(n log n)이며 기존 노드를 다시 연결합니다.

연결 리스트에서는 왜 퀵 정렬보다 병합 정렬을 선호하나요?

퀵 정렬은 노드를 다시 연결하여 리스트를 분할할 수 있지만, 좋은 피벗을 선택하려면 임의 접근이 필요하고, 맨 앞 요소를 피벗으로 선택하면 정렬된 리스트에서 비용이 O(n²)이 됩니다. 병합 정렬은 항상 절반으로 나누므로 어떤 입력에서도 O(n log n)을 유지합니다.

연결 리스트를 O(n log n) 시간과 O(1) 메모리로 정렬할 수 있나요?

네, 상향식 병합 정렬을 사용하면 됩니다. 길이가 1인 인접한 런을 병합한 다음, 길이가 2인 런, 그다음 길이가 4인 런을 병합하여 하나의 런이 목록 전체를 덮을 때까지 계속합니다. 선형 패스는 log n번 수행되며, 필요한 메모리는 노드 인덱스 몇 개뿐입니다.

def sortList(next, values):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

next = [3, -1, 4, 2, 1]
values = [4, 1, 3, 2, 5]

예상 출력

[1, 2, 3, 4, 5]