Python으로 연결 리스트가 엄격하게 증가하는지 확인하는 방법

개요

단일 연결 리스트(singly linked list)의 헤드(head)가 주어졌을 때, 노드들의 값이 엄격하게 오름차순(strictly ascending order)으로 정렬되어 있는지 확인하는 문제를 살펴보겠습니다.

예를 들어, 입력 리스트가 [2, 61, 105, 157]이라면 각 값이 이전 값보다 크므로 출력은 True가 됩니다. 반면 중간에 같거나 작아지는 값이 있다면 False를 반환해야 합니다.

문제 해결 접근 방식

이 문제는 재귀(recursion)를 활용하면 간단하게 해결할 수 있습니다. 다음 단계를 따릅니다:

• solve() 함수를 정의하고, 매개변수로 헤드 노드를 전달받습니다.
• 현재 노드의 다음 노드(head.next)가 null이라면 리스트의 끝에 도달한 것이므로 True를 반환합니다.
• 현재 노드의 값이 다음 노드의 값보다 크거나 같다면(head.val >= head.next.val) 엄격한 증가 조건을 만족하지 않으므로 False를 반환합니다.
• 위 두 조건에 해당하지 않으면 다음 노드를 인자로 하여 solve(head.next)를 재귀적으로 호출합니다.

구현 예제

class ListNode:
    def __init__(self, data, next = None):
        self.val = data
        self.next = next

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

class Solution:
    def solve(self, head):
        if head.next == None:
            return True
        if head.val >= head.next.val:
            return False
        return self.solve(head.next)

ob = Solution()
head = make_list([2,61,105,157])
print(ob.solve(head))

입력

[2,61,105,157]

출력

True

코드 설명

• ListNode 클래스: 연결 리스트의 각 노드를 표현합니다. 생성자는 데이터 값과 다음 노드 포인터를 받습니다.
• make_list 함수: 파이썬 리스트를 실제 연결 리스트 구조로 변환하는 유틸리티 함수입니다.
• Solution.solve 메서드: 재귀적으로 각 노드를 순회하며 현재 값이 다음 값보다 작은지만 검사합니다. 모든 노드를 통과하면 True를 반환합니다.

시간 및 공간 복잡도

• 시간 복잡도: O(n) — 리스트의 길이만큼 한 번씩 순회합니다.
• 공간 복잡도: O(n) — 재귀 호출로 인한 호출 스택이 사용됩니다. 깊은 리스트의 경우 반복문 기반 구현으로 O(1) 공간 복잡도로 개선할 수 있습니다.