문제 개요
단일 연결 리스트(singly linked list)와 하나의 목표 값(target)이 주어졌을 때, 값이 목표 값과 동일한 모든 노드를 삭제한 뒤의 연결 리스트를 반환하는 프로그램을 만들어 보겠습니다.
예를 들어 입력 리스트가 [5, 8, 2, 6, 5, 2, 9, 6, 2, 4]이고 목표 값이 2라면, 값이 2인 노드 세 개가 모두 제거되어 최종 결과는 [5, 8, 6, 5, 9, 6, 4]가 됩니다.
해결 알고리즘
이 문제는 새로운 리스트를 만들지 않고, 기존 리스트의 포인터(next)만 조작하여 노드를 건너뛰는 방식으로 효율적으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- 리스트의 시작 위치를
head변수에 저장합니다. - 현재 노드(
node)와 그 다음 노드(node.next)가 모두 존재하는 동안 아래 과정을 반복합니다.
- 다음 노드의 값이 목표 값과 같은 동안, 현재 노드의next포인터를 다다음 노드로 연결하여 해당 노드를 리스트에서 제외시킵니다.
-node를 다음 노드로 한 칸 이동합니다. - 반복이 끝난 후
head노드 자체의 값이 목표 값과 같다면head.next를 반환하고, 그렇지 않으면head를 그대로 반환합니다.
파이썬 구현 코드
아래는 위 알고리즘을 파이썬으로 구현한 전체 코드입니다.
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 print_list(head):
ptr = head
print('[', end='')
while ptr:
print(ptr.val, end=', ')
ptr = ptr.next
print(']')
class Solution:
def solve(self, node, target):
head = node
while node and node.next:
while node.next.val == target:
node.next = node.next.next
node = node.next
if head.val == target:
return head.next
else:
return head
ob = Solution()
head = make_list([5,8,2,6,5,2,9,6,2,4])
head = ob.solve(head, 2)
print_list(head)실행 결과 확인
입력
[5,8,2,6,5,2,9,6,2,4], target = 2
출력
[5, 8, 6, 5, 9, 6, 4]
코드 동작 원리
solve() 메서드는 리스트를 순회하면서 현재 노드의 다음 노드 값이 목표 값과 일치하는 경우, 해당 노드를 건너뛰고 다다음 노드에 직접 연결합니다. 이렇게 하면 목표 값과 일치하는 노드가 연속해서 여러 개 있더라도 한 번의 내부 반복으로 모두 제거할 수 있습니다.
순회가 끝난 뒤에는 첫 번째 노드(head) 자체가 목표 값과 일치하는지 별도로 검사합니다. 첫 노드는 앞선 순회 과정에서 처리되지 않기 때문입니다. 만약 첫 노드가 목표 값이라면 두 번째 노드부터 시작하는 리스트를 반환하고, 아니라면 원래의 head를 그대로 반환합니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n) — 리스트의 각 노드를 최대 한 번씩만 방문하므로 노드 개수에 비례합니다.
- 공간 복잡도: O(1) — 포인터 변수 몇 개만 사용하며 추가적인 자료구조가 필요하지 않습니다.