Reverse Linked List

Q: 연결 리스트를 제자리에서 어떻게 뒤집나요?

두 개의 포인터로 리스트를 순회합니다. prev 는 아무것도 가리키지 않는 상태에서 시작하고, node 는 헤드에서 시작합니다. 각 노드에서 다음 노드를 저장하고, 링크가 prev 를 가리키도록 한 다음, prev 와 node 를 한 단계씩 앞으로 이동합니다. node 가 끝에 도달하면 prev 가 뒤집힌 리스트의 헤드입니다.

Q: 연결 리스트를 뒤집는 시간 복잡도와 공간 복잡도는 얼마인가요?

반복 버전은 각 노드를 한 번씩 방문하며, 시간 복잡도는 O(n) 이고 포인터 3개를 유지하므로 추가 공간은 O(1) 입니다. 순서를 먼저 배열에 복사하는 방법도 시간 복잡도는 O(n) 이지만 추가 공간 O(n) 이 필요합니다. 재귀 버전은 호출 스택에 O(n) 의 공간을 사용합니다.

쉬움연결 리스트

+10

next 배열에 저장된 단일 연결 리스트가 주어집니다. 노드 i는 노드 next[i]를 가리키고, -1은 리스트의 끝을 나타내며, 헤드는 노드 0입니다. 노드는 리스트의 순서대로 저장되어 있지 않으므로 연결을 따라가세요.

모든 연결을 반대로 바꿔 리스트를 뒤집으세요. 그러면 기존의 마지막 노드가 헤드가 되고, 노드 0은 -1을 가리키는 마지막 노드가 됩니다. 입력과 길이가 같은 업데이트된 next 배열을 반환하세요.

함수

reverseList(next: integer-array) → integer-array

nextinteger-array: 각 노드가 연결되는 노드의 인덱스이며, 마지막 노드의 경우 -1입니다.
반환값integer-array: 뒤집힌 목록의 다음 배열

제약 조건

1 ≤ next.length ≤ 5000
각 next[i]는 -1이거나 0부터 next.length-1까지의 노드 인덱스입니다.
노드 0에서 시작하여 목록은 모든 노드를 정확히 한 번 방문한 다음 -1에 도달합니다. 순환은 없습니다.

예제

입력: next = [1, 2, 3, -1]
출력: [-1, 0, 1, 2]
설명: 목록은 0 → 1 → 2 → 3입니다. 이를 뒤집으면 3 → 2 → 1 → 0이므로, 노드 3은 2에 연결되고, 노드 2는 1에, 노드 1은 0에, 노드 0은 -1에 연결됩니다.

입력: next = [2, -1, 3, 1]
출력: [-1, 3, 0, 2]
설명: 목록은 0 → 2 → 3 → 1이며, 역순으로 나열하면 1 → 3 → 2 → 0입니다. 각 새 링크를 해당 노드의 인덱스에 기록하면 [-1, 3, 0, 2]가 됩니다. 배열 자체를 뒤집으면 [1, 3, -1, 2]가 되는데, 이는 같은 것이 아닙니다.

입력: next = [-1]
출력: [-1]
설명: 노드 하나는 그 자체의 역방향입니다. 머리이자 꼬리로 유지되며, 여전히 -1에 연결됩니다.

제출 시 숨은 테스트 +11개

후속 질문

목록에서 left 위치와 right 위치 사이의 부분만 뒤집고, 그 앞뒤에 있는 노드는 제자리에 그대로 둘 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

리스트를 뒤집어도 노드는 이동하지 않습니다. 각 링크의 방향을 바꾸는 것입니다. 문제는 노드의 링크가 리스트의 나머지 부분에 도달하는 유일한 방법이라는 점입니다. 따라서 링크를 덮어쓰는 순간 그 뒤에 있는 모든 것이 사라집니다. 먼저 순서를 적어 두어 이 문제를 피하거나, 링크를 바꾸기 전에 앞으로 나아갈 경로를 저장하는 세 개의 포인터를 사용해 한 번 순회할 수 있습니다.

순서를 적어 둔 다음 다시 연결하세요

핵심 아이디어

이 문제에서 포인터는 노드 인덱스이며, 앞으로 이동하는 것은 node = next[node]입니다. 0번 노드에서 시작해 -1에 도달할 때까지 따라가면서 지나치는 모든 노드를 적으세요. 두 번째 예시에서는 순서가 [0, 2, 3, 1]이 됩니다.

뒤집힌 리스트에서는 각 노드가 해당 순서에서 자기 앞에 있던 노드를 가리킵니다. 1은 3을 가리키고, 3은 2를, 2는 0을 가리킵니다. 순서의 첫 번째 노드, 즉 이전의 헤드는 앞에 오는 노드가 없으므로 -1을 가리킵니다. 새 배열에 이 연결 정보를 채운 다음 반환하세요.

각 연결 정보를 새 배열에 기록하므로, 아직 필요한 값이 덮어써지는 일이 없어 이 방법은 잘못 구현하기 어렵습니다. 시간은 O(n)이 걸리고, 순서와 새 배열을 저장하는 데 O(n)의 추가 메모리가 필요합니다.

알고리즘

노드 0에서 -1까지 이동하면서 각 노드를 order에 추가합니다.
같은 길이의 새 배열을 만듭니다.
order[0]의 항목을 -1로 설정합니다.
모든 k ≥ 1에 대해 order[k]의 항목을 order[k-1]로 설정합니다.
새 배열을 반환합니다.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

한 번에 링크를 뒤집으세요

핵심 아이디어

출발한 노드를 기억하고 있다면, 각 노드에 도달하는 순간 링크를 뒤집을 수 있습니다. 이전 노드인 prev를 기억해 두세요. 이전 헤드가 마지막 노드가 되므로 -1에서 시작합니다. node에서 링크 next[node]는 앞을 가리킵니다. 이 링크를 prev로 설정해 뒤를 가리키도록 하세요.

이렇게 값을 쓰면 앞으로 나아갈 유일한 경로가 사라지므로, 먼저 세 번째 변수 after = next[node]에 저장하세요. 그런 다음 링크를 뒤집고 두 포인터를 한 단계씩 이동합니다. prev = node, node = after. 어느 순간이든 뒤에 있는 노드들은 prev를 머리로 하는 뒤집힌 목록을 이루고, 앞에 있는 노드들은 아직 손대지 않은 나머지 노드로 node에서 시작합니다. node가 -1에 도달하면 모든 링크가 뒤집힌 것이고 prev가 새 헤드가 됩니다.

두 번째 예제에서는 포인터가 0, 2, 3, 1 노드를 차례로 지나며 next[0] = -1, next[2] = 0, next[3] = 2, next[1] = 3을 씁니다. 각 노드는 한 번씩 방문하므로 시간 복잡도는 O(n)이고, 메모리는 정수 세 개만 사용하므로 O(1)입니다.

알고리즘

prev = -1과 node = 0을 설정합니다.
node가 -1이 아닌 동안 after = next[node]를 저장합니다.
next[node] = prev를 설정합니다.
다음으로 이동합니다: prev = node를 설정한 다음 node = after를 설정합니다.
next를 반환합니다.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

함정과 경계 사례

여기서 발생하는 버그는 거의 모두 세 번의 대입 순서나 목록의 양 끝 두 곳에 관한 것입니다.

next[node]를 저장하기 전에 덮어씁니다. next[node] = prev를 실행하면 기존의 다음 링크가 사라져, 다음 노드로 이어지는 대신 순회가 뒤로 되돌아갑니다.
prev를 -1이 아닌 다른 값으로 시작합니다. 기존 헤드는 새 목록의 끝이어야 합니다. 0으로 시작하면 노드 0이 자기 자신을 가리킵니다.
링크 대신 배열을 뒤집습니다. 노드는 목록 순서대로 저장되어 있지 않고, 답에서는 각 노드가 자신의 인덱스에 그대로 있습니다. 값만 바뀝니다. [2, -1, 3, 1]을 뒤집으면 [1, 3, -1, 2]가 되며, [-1, 3, 0, 2]가 아닙니다.
next[node] != -1을 조건으로 하는 루프를 사용해 노드 하나를 남겨 두고 중단합니다. 마지막 노드의 링크도 바꿔야 하므로 node != -1인 동안 반복하세요.
긴 목록을 재귀로 뒤집습니다. 노드가 5000개인 목록은 중첩 호출이 5000번 필요하므로 Python의 제한인 1000회를 넘습니다.
배열 인덱스가 1부터 시작하는 Lua와 R에서 오프셋을 잊습니다. 노드 인덱스는 0부터 유지하고 next[node + 1]을 읽으세요. Ruby와 R에서는 next라는 단어를 사용할 수 없으므로, 해당 언어의 예제에서는 매개변수 이름을 next_로 지정합니다.

자주 묻는 질문4

연결 리스트를 제자리에서 어떻게 뒤집나요?

두 개의 포인터로 리스트를 순회합니다. prev는 아무것도 가리키지 않는 상태에서 시작하고, node는 헤드에서 시작합니다. 각 노드에서 다음 노드를 저장하고, 링크가 prev를 가리키도록 한 다음, prev와 node를 한 단계씩 앞으로 이동합니다. node가 끝에 도달하면 prev가 뒤집힌 리스트의 헤드입니다.

연결 리스트를 뒤집는 시간 복잡도와 공간 복잡도는 얼마인가요?

반복 버전은 각 노드를 한 번씩 방문하며, 시간 복잡도는 O(n)이고 포인터 3개를 유지하므로 추가 공간은 O(1)입니다. 순서를 먼저 배열에 복사하는 방법도 시간 복잡도는 O(n)이지만 추가 공간 O(n)이 필요합니다. 재귀 버전은 호출 스택에 O(n)의 공간을 사용합니다.

연결 리스트를 재귀적으로 뒤집을 수 있나요?

네. 헤드 뒤의 모든 것을 뒤집은 다음, 헤드의 기존 다음 노드가 헤드를 가리키도록 하고 헤드의 링크를 아무것도 가리키지 않도록 설정하세요. 읽기에는 좋지만 노드마다 중첩 호출을 하나씩 수행하므로, 목록이 길면 호출 스택이 넘칠 수 있습니다. Python은 기본적으로 호출 횟수가 1000회에 도달하면 중단하며, 노드가 5000개인 목록은 이 제한을 초과합니다.

연결 리스트를 뒤집을 때 포인터가 세 개 필요한 이유는 무엇인가요?

노드의 링크를 뒤집으려면 해당 노드와 그 앞의 노드가 필요하며, 이는 포인터 두 개입니다. 세 번째 포인터에는 그 뒤의 노드를 저장해야 합니다. 링크를 뒤집으면 리스트의 나머지 부분을 가리키는 유일한 참조가 사라지기 때문입니다. 이 포인터가 없으면 순회를 계속할 수 없습니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

next = [1, 2, 3, -1]

기대값

[-1, 0, 1, 2]