연결 리스트(Linked List)가 하나 주어졌을 때, 이 리스트의 길이가 짝수인지 홀수인지 판별하는 문제를 살펴보겠습니다.
예를 들어 입력이 head = [5,8,7,4,3,6,4,5,8]과 같다면, 노드가 총 9개이므로 출력은 Odd(홀수)가 됩니다.
문제 해결 접근 방식
이 문제는 두 칸씩 건너뛰는 포인터 기법을 사용하면 추가 메모리 없이 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 노드(head)가 null이 아니고, 다음 노드도 null이 아닌 동안 반복합니다.
- 반복할 때마다 포인터를 두 칸 앞으로 이동시킵니다(
head := head.next.next). - 반복이 끝난 후 head가 null이라면 노드 수가 짝수이므로 "Even"을 반환합니다.
- 그렇지 않고 마지막 노드에 머물러 있다면 노드 수가 홀수이므로 "Odd"를 반환합니다.
이 방식은 리스트를 한 번만 순회하면서 두 노드씩 이동하므로 시간 복잡도는 O(n)이며, 별도의 카운터 변수나 추가 공간이 필요하지 않다는 장점이 있습니다.
예제 코드
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 def solve(head): while head != None and head.next != None: head = head.next.next if head == None: return "Even" return "Odd" head = make_list([5,8,7,4,3,6,4,5,8]) print(solve(head))
입력
[5,8,7,4,3,6,4,5,8]
출력
Odd
동작 원리 상세 설명
위 코드에서 solve() 함수의 동작 과정을 단계별로 살펴보면 다음과 같습니다.
- 초기 상태: head는 첫 번째 노드(값 5)를 가리킵니다.
- 1회 반복: head와 head.next가 모두 존재하므로, head는 세 번째 노드(값 7)로 이동합니다.
- 2회 반복: head는 다섯 번째 노드(값 3)로 이동합니다.
- 3회 반복: head는 일곱 번째 노드(값 4)로 이동합니다.
- 4회 반복: head는 아홉 번째 노드(값 8)로 이동합니다.
- 반복 종료: 이제 head.next가 null이므로 루프가 종료됩니다. head가 null이 아니므로 "Odd"를 반환합니다.
반대로 노드 개수가 짝수라면, 두 칸씩 이동하던 포인터가 결국 null에 도달하게 되어 "Even"이 반환됩니다. 빈 리스트(null)가 입력되는 경우에도 while 조건이 처음부터 거짓이 되고, head가 null이므로 "Even"이 올바르게 반환됩니다.