Python으로 연결 리스트에서 인접 노드 간 절대 차이가 1인지 확인하는 방법

정수 값을 저장하는 단일 연결 리스트(singly linked list)가 있다고 가정해 봅시다. 이때, 서로 인접한 두 노드 값의 절대 차이(abs)가 항상 1인지 확인해야 하는 문제입니다.

예를 들어, 리스트가 다음과 같이 구성되어 있다면:

start_node → 5 → 6 → 7 → 8 → 7 → 6 → 5 → 4

모든 인접 노드의 차이가 정확히 1이므로 출력 결과는 True가 됩니다.

문제 해결 접근 방식

이 문제는 다음 단계에 따라 해결할 수 있습니다.

• 임시 포인터 temp를 시작 노드로 초기화합니다.
• temp가 null이 아닐 때까지 반복합니다.
  • temp.link가 null이면 마지막 노드에 도달한 것이므로 반복을 종료합니다.
• |temp.value − temp.link.value|(인접 노드 값의 절대 차이)가 1이 아니라면 즉시 False를 반환합니다.
• 그렇지 않으면 temp를 다음 노드(temp.link)로 이동시킵니다.
• 모든 검사를 통과하면 True를 반환합니다.

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.

예제 코드

아래 구현을 통해 더 자세히 살펴보겠습니다.

import math

class link_node:
    def __init__(self, value):
        self.value = value
        self.link = None

def create_node(value):
    temp = link_node(value)
    temp.value = value
    temp.link = None
    return temp

def make_list(elements):
    head = link_node(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = link_node(element)
    return head

def solve(start_node):
    temp = start_node
    while (temp):
        # 마지막 노드에 도달하면 종료
        if (temp.link == None):
            break
        # 인접 노드 간 절대 차이가 1이 아니면 False 반환
        if (abs((temp.value) - (temp.link.value)) != 1):
            return False
        temp = temp.link
    return True

start_node = make_list([5, 6, 7, 8, 7, 6, 5, 4])
print(solve(start_node))

입력

[5, 6, 7, 8, 7, 6, 5, 4]

출력

True

코드 설명

• link_node 클래스는 노드의 값(value)과 다음 노드를 가리키는 링크(link)를 정의합니다.
• make_list 함수는 입력 리스트를 순회하며 연결 리스트를 생성하고 헤드 노드를 반환합니다.
• solve 함수는 현재 노드와 다음 노드의 값 차이를 검사하여 조건을 만족하지 않으면 즉시 False를 반환합니다.

주어진 예제에서는 5→6→7→8→7→6→5→4 순서로 모든 인접 값의 차이가 1이므로 최종적으로 True가 출력됩니다.