Palindrome Linked List

Q: 회문 연결 리스트 검사와 시간 복잡도는 어떻게 되나요?

각 값은 비교해야 하므로, L 개의 노드가 있는 리스트에서 모든 접근 방식의 시간 복잡도는 O(L) 입니다. 값을 배열이나 스택에 복사하면 추가 메모리 O(L) 을 사용하고, 제자리에서 두 번째 절반을 뒤집으면 O(1) 을 사용합니다.

Q: 빠른 포인터와 느린 포인터는 연결 리스트의 중간을 어떻게 찾나요?

둘 다 헤드에서 시작하며, 빠른 포인터는 느린 포인터가 한 걸음 이동할 때마다 두 걸음씩 이동합니다. 빠른 포인터가 끝에 도달하면 전체 목록을 이동한 것이고, 느린 포인터는 그 절반을 이동한 것입니다.

Q: 목록의 절반을 뒤집으면 입력이 손상되나요?

네, 후반부의 링크를 변경하며, 대부분의 언어에서 해당 배열은 호출자의 배열입니다. 목록이 여전히 필요하다면 일찍 반환하지 말고 비교를 마친 다음, 후반부를 다시 뒤집으세요. 중간 노드는 여전히 후반부의 첫 번째 노드를 가리키므로 목록은 O(1) 추가 메모리만으로 다시 온전한 상태가 됩니다.

쉬움연결 리스트 빠른 포인터와 느린 포인터 투 포인터

+10

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

헤드에서 끝까지 읽은 값이 끝에서 헤드까지 읽은 값과 같으면 true를 반환하고, 그렇지 않으면 false를 반환하세요.

함수

isPalindrome(next: integer-array, values: integer-array) → boolean

nextinteger-array: 각 노드가 연결하는 노드의 인덱스 또는 마지막 노드의 경우 -1
valuesinteger-array: 각 노드가 보유한 값
반환값boolean: 목록을 양방향으로 읽었을 때 동일하면 true

제약 조건

1 ≤ L ≤ 5000이며, 여기서 L은 next와 values의 길이입니다.
-100 ≤ values[i] ≤ 100
각 next[i]는 -1이거나 0부터 L-1까지의 노드 인덱스입니다.
노드 0에서 시작해 목록은 각 노드를 정확히 한 번씩 방문한 다음 -1에 도달합니다. 사이클은 없습니다.

예제

입력: next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
출력: true
설명: 링크는 노드 0, 4, 1, 3, 2를 방문하므로, 목록은 3, 1, 4, 1, 3입니다. 두 개의 3은 일치하고, 두 개의 1도 일치하며, 가운데의 4는 확인할 짝이 없습니다.

입력: next = [2, -1, 3, 1]values = [4, 4, 9, 9]
출력: true
설명: 목록은 노드 0, 2, 3, 1을 방문하고 4, 9, 9, 4를 읽으며, 양방향에서 동일합니다.

입력: next = [2, -1, 1]values = [1, 2, 1]
출력: false
설명: 배열 values는 [1, 2, 1]이지만, 리스트는 노드 0, 2, 1을 방문하고 1, 1, 2를 읽습니다. 이를 거꾸로 하면 2, 1, 1이므로 답은 false입니다.

후속 질문

O(L) 시간과 O(1) 추가 메모리로 할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

회문 검사는 각 값을 반대쪽 끝에서 대칭되는 값과 짝지어 확인합니다. 단일 연결 리스트는 앞으로만 순회하므로, 어려운 점은 뒤쪽 절반을 역순으로 읽는 것입니다. 배열에 복사하면 O(L) 메모리가 필요합니다. 여기서 L은 노드의 개수입니다. 뒤쪽 절반의 링크를 뒤집으면 O(1) 메모리로 처리할 수 있습니다.

값을 배열에 복사하기

핵심 아이디어

여기서 포인터는 노드 인덱스이고, 다음 노드로 이동하는 방법은 node = next[node]입니다. 리스트를 한 번 순회하면서 각 값을 배열에 복사하면, 양쪽 끝에서 모두 읽을 수 있습니다. 첫 번째 값과 마지막 값을 비교하고, 두 인덱스를 가운데 쪽으로 이동하세요. 값이 일치하지 않으면 false를 반환합니다. 길이가 홀수이면 가운데 값은 자기 자신과 짝을 이룹니다.

모든 값을 읽어야 하므로 O(L) 시간이 최선입니다. 추가 정수 L개가 필요합니다.

알고리즘

노드 0에서 -1까지 이동하며 각 values[node]를 배열에 추가합니다.
i = 0으로 설정하고 j를 마지막 인덱스로 설정합니다.
i < j인 동안 두 값이 다르면 false를 반환하고, 그렇지 않으면 i를 증가시키고 j를 감소시킵니다.
true를 반환합니다.

def isPalindrome(next, values):
    # Write the values out in list order.
    seq = []
    node = 0
    while node != -1:
        seq.append(values[node])
        node = next[node]
    # Compare from both ends toward the middle.
    i = 0
    j = len(seq) - 1
    while i < j:
        if seq[i] != seq[j]:
            return False
        i += 1
        j -= 1
    return True

제자리에서 두 번째 절반을 뒤집으세요

핵심 아이디어

뒷부분을 복사하는 대신 링크를 뒤집습니다. 그러면 이전 마지막 노드에서 시작해 가운데를 향해 이동할 수 있습니다. 가운데를 찾으려면 fast가 앞에 링크를 두 개 가지고 있는 동안 slow가 링크 하나를 이동할 때마다 fast를 링크 두 개씩 이동시킵니다. slow는 첫 번째 절반의 마지막 노드에서 멈춥니다. L이 홀수이면 이 노드는 가운데 노드입니다. 첫 번째 예제에서 slow는 0 → 4 → 1로 이동하고 fast는 0 → 1 → 2로 이동하므로, slow는 4에서 멈춥니다.

slow 다음의 노드들을 뒤집은 다음, 머리에서 시작하는 left와 뒤집힌 절반에서 시작하는 right를 함께 이동시킵니다. 3과 3을 비교하고, 이어서 1과 1을 비교합니다. 뒤집힌 절반은 첫 번째 절반보다 길지 않으므로, right가 끝날 때 멈추면 필요한 쌍만 정확히 비교합니다. 각 단계에서는 최대 L개의 노드를 순회하고 정수 몇 개만 저장합니다. R에서는 next_를 변경할 때 벡터가 한 번 복사되므로, R은 O(L) 메모리를 사용합니다.

알고리즘

slow = fast = 0으로 설정합니다. next[fast]와 next[next[fast]]가 모두 -1이 아닌 동안 slow는 링크 하나만큼, fast는 두 링크만큼 이동합니다.
next[slow]에서 시작하는 리스트를 뒤집습니다. 각 노드에서 링크를 저장하고, 해당 노드가 prev를 가리키도록 한 다음 prev와 노드를 앞으로 이동합니다.
left = 0으로 설정하고, 뒤집힌 절반의 헤드인 prev를 right로 설정합니다.
right != -1인 동안 값이 일치하지 않으면 false를 반환하고, 그렇지 않으면 두 포인터를 모두 링크 하나만큼 이동합니다.
true를 반환합니다.

def isPalindrome(next, values):
    # Find the middle: fast moves two links for every one link slow moves.
    slow = 0
    fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    # slow is the last node of the first half (the middle node when the length is odd).
    # Reverse the links of the second half.
    prev = -1
    node = next[slow]
    while node != -1:
        after = next[node]
        next[node] = prev
        prev = node
        node = after
    # prev is the old last node, now the head of the reversed half.
    left = 0
    right = prev
    while right != -1:
        if values[left] != values[right]:
            return False
        left = next[left]
        right = next[right]
    return True

함정과 경계 사례

리스트가 아니라 배열을 확인하는 것. 세 번째 예시에서 values는 [1, 2, 1]이지만, 리스트는 1, 1, 2로 되어 있습니다.
next[fast] != -1만 검사하는 것. 그러면 fast가 -1로 이동해 next[-1]을 읽을 수 있습니다. 대부분의 언어에서는 범위를 벗어나고, Python과 Ruby에서는 오류 없이 마지막 항목을 읽습니다.
right가 아니라 left가 끝날 때까지 비교하는 것. 중간 노드는 여전히 이전의 두 번째 절반을 가리키므로, 헤드에서 시작하는 순회가 더 깁니다.
나머지 리스트를 잃게 되는, 역순으로 바꾸는 도중 값을 저장하기 전에 next[node]를 덮어쓰는 것.
배열 인덱스가 1부터 시작하는 Lua와 R에서 0부터 시작하는 노드 ID에 대해 next[node]를 읽는 것. next[node + 1]을 읽으세요.

자주 묻는 질문3

회문 연결 리스트 검사와 시간 복잡도는 어떻게 되나요?

각 값은 비교해야 하므로, L개의 노드가 있는 리스트에서 모든 접근 방식의 시간 복잡도는 O(L)입니다. 값을 배열이나 스택에 복사하면 추가 메모리 O(L)을 사용하고, 제자리에서 두 번째 절반을 뒤집으면 O(1)을 사용합니다.

빠른 포인터와 느린 포인터는 연결 리스트의 중간을 어떻게 찾나요?

둘 다 헤드에서 시작하며, 빠른 포인터는 느린 포인터가 한 걸음 이동할 때마다 두 걸음씩 이동합니다. 빠른 포인터가 끝에 도달하면 전체 목록을 이동한 것이고, 느린 포인터는 그 절반을 이동한 것입니다.

목록의 절반을 뒤집으면 입력이 손상되나요?

네, 후반부의 링크를 변경하며, 대부분의 언어에서 해당 배열은 호출자의 배열입니다. 목록이 여전히 필요하다면 일찍 반환하지 말고 비교를 마친 다음, 후반부를 다시 뒤집으세요. 중간 노드는 여전히 후반부의 첫 번째 노드를 가리키므로 목록은 O(1) 추가 메모리만으로 다시 온전한 상태가 됩니다.

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

테스트 #1

테스트 #2

테스트 #3

인자들

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

예상 출력

true