요소들이 저장된 단일 연결 리스트(singly linked list)가 있다고 가정해 봅시다. 여기에 삽입할 위치를 나타내는 값 pos와 새로 추가할 값 val이 주어집니다. 우리가 해야 할 작업은 연결 리스트의 pos 인덱스 앞에 val 값을 삽입하는 것입니다.
예를 들어 입력이 다음과 같다면,
- nums = [1, 5, 3, 6, 8]
- pos = 3
- val = 7
출력 결과는 [1, 5, 3, 7, 6, 8]이 됩니다. 즉, 인덱스 3에 있던 값 6 앞에 새로운 값 7이 삽입되는 것입니다.
해결 알고리즘
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 삽입할 값
val과 동일한 값을 가지는 새로운 노드new를 생성합니다. - 만약
pos가 0이라면, 삽입 위치가 리스트의 맨 앞입니다. 이 경우new의 next가 기존의 헤드 노드(list_head)를 가리키도록 한 후,new를 반환합니다. pos가 0이 아니라면, 임시 포인터temp를 헤드 노드로 설정합니다.temp가 null이 아니고pos가 1이 아닌 동안 다음을 반복합니다.temp를 다음 노드로 이동합니다.pos를 1씩 감소시킵니다.
- 반복이 끝나면
temp는 삽입할 위치의 바로 이전 노드를 가리킵니다. 이제new의 next가temp의 next를 가리키도록 합니다. temp의 next가new를 가리키도록 변경하여 새 노드를 연결합니다.- 마지막으로
list_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(']')
def solve(list_head, pos, val):
new = ListNode(val)
if pos == 0:
new.next = list_head
return new
temp = list_head
while temp and pos != 1:
temp = temp.next
pos -= 1
new.next = temp.next
temp.next = new
return list_head
nums = [1, 5, 3, 6, 8]
pos = 3
val = 7
list_head = make_list(nums)
list_head = solve(list_head, pos, val)
print_list(list_head)입력
[1,5,3,6,8], 3, 7
출력
[1, 5, 3, 7, 6, 8]
동작 원리 정리
핵심 로직을 간단히 살펴보면 다음과 같습니다. 먼저 make_list 함수는 일반 파이썬 리스트를 연결 리스트로 변환하고, solve 함수는 주어진 위치 앞에 새 노드를 삽입합니다. 위치가 0인 경우에는 헤드 노드 자체가 교체되므로 새 노드를 반환하지만, 그 외의 경우에는 목표 위치 직전 노드까지 이동한 뒤 두 개의 포인터(next 참조)만 조정하면 삽입이 완료됩니다. 이러한 포인터 재연결 작업은 O(1)의 시간 복잡도로 수행되며, 전체 알고리즘은 목표 위치까지 탐색하는 데 O(n)의 시간 복잡도를 가집니다.