Reorder List
같은 길이의 두 배열에 저장된 단일 연결 리스트가 주어집니다. 노드 i에는 값 values[i]가 있고 노드 next[i]를 가리킵니다. -1은 리스트의 끝을 나타내며, 헤드는 노드 0입니다. 노드가 리스트 순서대로 저장되어 있지 않으므로 링크를 따라가세요.
리스트 순서대로 노드에 L0, L1, ..., Lk라는 이름을 붙입니다. 리스트의 순서를 L0, Lk, L1, Lk-1, L2, Lk-2, ...가 되도록 바꾸세요. 즉, 첫 번째 노드, 마지막 노드, 두 번째 노드, 끝에서 두 번째 노드 순으로 이어집니다. 새 순서대로 값을 반환하세요.
함수
- 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에 도달합니다. 순환은 없습니다.
예제
- 입력
- next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
- 출력
- [1, 5, 2, 4, 3]
- 설명
- 노드
0에서 링크를 따라가면 목록은1, 2, 3, 4, 5입니다. 첫 번째, 마지막, 두 번째, 끝에서 두 번째 항목은1, 5, 2, 4이고, 가운데 값인3은 마지막에 옵니다.
- 입력
- next = [2, 3, 1, -1]values = [10, 30, 20, 40]
- 출력
- [10, 40, 20, 30]
- 설명
- 목록은 노드
0, 2, 1, 3을 방문하고10, 20, 30, 40을 읽습니다. 처음과 마지막 값은10, 40이고, 그다음 안쪽 쌍은20, 30입니다.
- 입력
- next = [-1]values = [7]
- 출력
- [7]
- 설명
- 노드가 하나인 리스트는 이동할 것이 없으므로 답은
[7]입니다.
후속 질문
추가 메모리 O(1)만 사용하여 링크 자체의 순서를 바꿀 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
1, 2, 3, 4, 5, 6의 목표 순서를 작성하세요. 목록의 앞쪽 절반에 해당하는 노드는 무엇이며, 뒤쪽 절반의 노드들은 어떤 순서로 나타나나요?뒤쪽 절반이 역순으로 나타납니다:
6, 5, 4. 뒤쪽 절반이 뒤집혀 있었다면, 정답은 각 목록에서 노드를 하나씩 번갈아 가져와 합친 두 목록이었을 것입니다.한 링크씩 이동하는 느린 포인터와 두 링크씩 이동하는 빠른 포인터를 사용해 중간을 찾으세요. 중간 다음에서 리스트를 자르고, 두 번째 부분의 링크 방향을 바꿔 뒤집은 다음, 두 부분을 노드별로 번갈아 엮으세요.
풀이
새로운 순서는 앞과 뒤를 번갈아 가지만, 단일 연결 리스트는 앞으로만 순회합니다. 작업을 세 가지 표준 리스트 연산으로 나누세요. 느린 포인터와 빠른 포인터로 중간을 찾고, 뒤쪽 절반을 뒤집은 다음, 두 절반을 노드 하나씩 번갈아 엮습니다.
꼬리를 한 번에 노드 하나씩 앞으로 이동합니다
핵심 아이디어
여기서 포인터는 노드 인덱스이고, 앞으로 이동하는 것은 node = next[node]입니다. 첫 번째 노드 다음에 마지막 노드가 오므로, 마지막 노드를 분리해 현재 노드 뒤에 삽입한 다음 두 노드 더 앞으로 이동해 반복합니다. 1, 2, 3, 4, 5의 경우 1, 5, 2, 3, 4가 되고, 그다음에는 1, 5, 2, 4, 3이 됩니다. 현재 노드 뒤에 노드가 두 개 미만으로 남으면 멈춥니다.
마지막 노드 앞의 노드를 찾으려면 매번 끝까지 순회해야 합니다. 순회할 때마다 두 노드씩 줄어들며, 총 이동 횟수는 약 n²/4입니다. 노드 4000개라면 400만 번입니다.
알고리즘
cur = 0으로 설정합니다.cur뒤에 노드가 두 개 이상 있는 동안,next[next[before]] == -1이 될 때까지cur부터before를 따라 이동합니다. 그러면tail = next[before]가 마지막 노드입니다.next[before] = -1로 연결을 끊은 다음, 삽입합니다:next[tail] = next[cur]및next[cur] = tail.cur를next[tail]로 이동하고 반복합니다.- 노드
0부터 따라가며 값을 수집합니다.
def reorderList(next, values):
cur = 0
# While at least two nodes follow cur, move the last node right after cur.
while next[cur] != -1 and next[next[cur]] != -1:
before = cur
while next[next[before]] != -1: # find the node before the tail
before = next[before]
tail = next[before]
next[before] = -1
next[tail] = next[cur]
next[cur] = tail
cur = next[tail]
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result값을 복사하고 양쪽 끝에서 읽기
핵심 아이디어
배열은 한 번의 순회로 마지막 요소에 도달합니다. 첫 번째 예시의 [1, 2, 3, 4, 5]처럼 목록 순서대로 값을 복사한 다음, 앞에서부터는 lo를, 뒤에서부터는 hi를 읽습니다. lo를 가져오고, hi를 가져온 뒤, lo < hi인 동안 둘 다 가운데 쪽으로 이동합니다. 그러면 1, 5, 2, 4가 됩니다. 길이가 홀수이면 둘 다 가운데의 3에서 만나며, 이 값은 마지막에 옵니다.
시간 복잡도는 O(n)이고 추가 메모리는 O(n)이며, 링크는 절대 바뀌지 않습니다.
알고리즘
- 노드
0에서 시작해 각 값을inOrder에 추가합니다. lo = 0으로 설정하고hi를 마지막 인덱스로 설정합니다.lo < hi인 동안inOrder[lo]와inOrder[hi]를 추가한 다음,lo를 증가시키고hi를 감소시킵니다.lo == hi이면 가운데 값을 추가합니다.
def reorderList(next, values):
# Write the values out in list order.
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
# Take from the front and the back in turn.
result = []
lo, hi = 0, len(in_order) - 1
while lo < hi:
result.append(in_order[lo])
result.append(in_order[hi])
lo += 1
hi -= 1
if lo == hi: # odd length: the middle value comes last
result.append(in_order[lo])
return result가운데를 찾고, 뒤쪽 절반을 뒤집고, 엮기
핵심 아이디어
1, 2, 3, 4, 5, 6의 답은 1, 6, 2, 5, 3, 4입니다. 앞부분 1, 2, 3을 순서대로, 뒷부분 4, 5, 6을 거꾸로 읽어 번갈아 배치한 결과입니다. 따라서 목록을 가운데에서 자르고, 뒷부분을 뒤집은 다음, 두 부분을 번갈아 엮으면 됩니다.
slow는 링크를 하나씩 이동하고 fast는 두 개씩 이동하므로, slow는 앞부분의 마지막 노드인 3에서 멈춥니다. 노드가 5개일 때와 6개일 때 모두 마찬가지입니다. 그 뒤에서 자르면 길이가 홀수일 때 앞부분에 노드가 하나 더 포함되고, 그 노드가 답의 마지막이 됩니다. 뒷부분의 노드가 모두 소진될 때까지 두 부분에서 번갈아 노드를 하나씩 가져와 엮습니다.
각 노드는 상수 횟수만큼 방문하며, 메모리는 인덱스 몇 개만 사용합니다. R은 링크 벡터가 처음 변경될 때 복사하므로, R에서 메모리 복잡도는 O(n)입니다.
알고리즘
next[fast]와next[next[fast]]가-1이 아닌 동안slow는 한 링크,fast는 두 링크씩 이동합니다.second = next[slow]로 설정한 다음,next[slow] = -1로 설정합니다.second에서 시작하는 리스트를 뒤집습니다. 새로운 헤드는prev입니다.- 교차 연결합니다.
second가-1이 아닌 동안first를second에 연결하고,second를 이전의next[first]에 연결한 다음, 둘 다 다음 위치로 이동합니다. - 노드
0부터 순회하며 값을 모읍니다.
def reorderList(next, values):
# 1. Find the middle: slow stops on the last node of the first half.
slow = fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
# 2. Reverse the second half.
prev = -1
while second != -1:
after = next[second]
next[second] = prev
prev = second
second = after
# 3. Weave: one node from the front half, one from the reversed back half.
first, second = 0, prev
while second != -1:
first_after, second_after = next[first], next[second]
next[first] = second
next[second] = first_after
first, second = first_after, second_after
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result
함정과 경계 사례
- 목록을 중간에서 자르지 않음.
next[slow] = -1이 없으면 앞부분이 여전히 뒷부분을 가리키므로, 목록을 엮은 후 목록이 자기 자신을 순환하게 됩니다. - 저장하기 전에 링크를 덮어씀. 뒤집기와 엮기 과정에서는 먼저
next[node]를 변수에 읽어 두세요. 그렇지 않으면 목록의 나머지 부분을 잃게 됩니다. - 앞부분이 끝날 때까지 엮음. 길이가 홀수이면 해당 루프가 한 번 더 실행되어
second가-1인 상태에서next[-1]을 읽습니다. - 배열의 순서를 목록의 순서로 읽음. 첫 번째 예시에서
values는[1, 3, 5, 2, 4]이지만, 목록은1, 2, 3, 4, 5순서입니다. - Lua와 R에서는 배열 인덱스가 1부터 시작합니다. 노드 인덱스는 0부터 시작하도록 유지하고
next[node + 1]을 읽으세요.
자주 묻는 질문3
목록의 후반부를 뒤집는 이유는 무엇인가요?
답은 뒤쪽 절반을 마지막 노드에서 첫 번째 노드 방향으로 읽지만, 단일 연결 리스트는 앞으로만 이동합니다. 뒤쪽 절반을 한 번 O(n)의 시간 복잡도로 뒤집으면 병합 과정에서 두 절반을 모두 앞으로 이동하며 순회할 수 있습니다.
Reorder List의 시간 복잡도는 얼마인가요?
제자리 방식은 O(n) 시간과 O(1) 추가 메모리로 실행됩니다. 가운데를 찾고, 뒤집고, 교차 배치하는 과정에서 각 노드를 일정한 횟수만큼 방문하기 때문입니다. 값을 배열에 복사하는 방법도 O(n) 시간이 걸리지만 O(n) 메모리가 필요하고, 꼬리를 한 번에 노드 하나씩 앞으로 이동하는 방법은 O(n²) 시간이 걸립니다.
목록에 노드 수가 짝수일 때 가운데는 어디인가요?
앞쪽 절반의 마지막 노드에서 느린 포인터를 멈추세요. 노드가 여섯 개이면 각 절반은 세 개씩이고, 다섯 개이면 세 개와 두 개입니다. 이때 남는 노드가 답의 끝이 되며, 순서상 중간값이 놓이는 위치입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def reorderList(next, values):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
next = [3, 4, -1, 1, 2] values = [1, 3, 5, 2, 4]
예상 출력
[1, 5, 2, 4, 3]