문제 개요
단일 연결 리스트(singly linked list)가 하나 주어졌다고 가정해 보겠습니다. 우리가 해야 할 작업은 이 연결 리스트의 길이, 즉 포함된 노드의 총 개수를 구하는 것입니다. 이 연결 리스트의 각 노드는 다음 노드를 가리키는 next 필드와 자기 자신의 값을 저장하는 val 필드를 가지고 있습니다.
예를 들어 입력이 [2 -> 4 -> 5 -> 7 -> 8 -> 9 -> 3]과 같은 형태로 주어진다면, 노드가 총 7개이므로 결과값은 7이 됩니다.
접근 방법
연결 리스트의 길이를 구하는 가장 기본적이고 직관적인 방법은 리스트를 처음부터 끝까지 순회(traverse)하면서 개수를 세는 것입니다. 알고리즘은 다음과 같습니다.
- 카운터 변수 count를 0으로 초기화합니다.
- 현재 노드가 null이 아닌 동안 다음 과정을 반복합니다.
- count를 1씩 증가시킵니다.
- node를 다음 노드(node.next)로 이동시킵니다.
- 반복이 종료되면 count를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n)(n은 노드의 개수)이며, 추가 변수만 사용하기 때문에 공간 복잡도는 O(1)입니다.
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
예제 코드
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, node):
count = 0
while node:
count +=1
node=node.next
return count
ob = Solution()
head = make_list([2,4,5,7,8,9,3])
print(ob.solve(head))
입력
[2,4,5,7,8,9,3]
출력
7
위 코드에서 Solution 클래스의 solve 메서드는 헤드 노드부터 시작하여 next 포인터를 따라 한 칸씩 이동하면서 노드의 개수를 셉니다. 모든 노드를 지나면 node가 None이 되어 반복문이 종료되고, 그 시점까지 세어진 count 값이 곧 연결 리스트의 길이가 됩니다.