문제 개요
길이가 각각 m과 n인 두 개의 연결 리스트 L1과 L2가 있고, 위치를 나타내는 값 a와 b가 주어집니다. 이때 L1의 a번째 노드부터 b번째 노드까지를 제거한 뒤, 그 자리에 L2 전체를 끼워 넣어 하나의 리스트로 병합해야 합니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
- L1 = [1,5,6,7,1,6,3,9,12]
- L2 = [5,7,1,6]
- a = 3, b = 6
이 경우 L1의 3번째 노드(7)부터 6번째 노드(6)까지가 제거되고, 그 사이에 L2가 들어가므로 출력은 [1, 5, 6, 5, 7, 1, 6, 9, 12]가 됩니다.
해결 접근 방법
이 문제는 포인터(참조) 조작만으로 O(m + n) 시간 안에 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- L2의 머리 노드(head2)를 저장하고, 임시 포인터 temp를 L2로 설정합니다.
- temp를 리스트 끝까지 이동시켜 L2의 마지막 노드(tail2)를 찾습니다.
- 카운트 변수 count를 0으로 초기화하고, temp를 L1의 시작점으로 이동합니다.
- L1을 순회하면서 다음 두 지점을 기록합니다.
- count가 a-1일 때의 노드 → end1 (삭제 구간 바로 앞 노드)
- count가 b+1일 때의 노드 → start3 (삭제 구간 바로 뒤 노드)
- end1의 next를 head2에 연결하여 L2의 앞부분을 붙입니다.
- tail2의 next를 start3에 연결하여 L2의 뒷부분을 이어줍니다.
- 수정된 L1을 반환합니다.
핵심은 L1의 노드를 실제로 삭제하는 것이 아니라, 포인터 연결만 변경하여 삭제된 것처럼 만드는 것입니다. 따라서 추가적인 메모리 사용 없이 효율적으로 처리할 수 있습니다.
파이썬 구현 예제
아래 코드는 위 알고리즘을 그대로 구현한 것입니다. 연결 리스트 생성 함수와 출력 함수도 함께 포함되어 있어 바로 실행해 볼 수 있습니다.
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(L1, L2, a, b):
# L2의 마지막 노드(tail2) 찾기
head2 = temp = L2
while temp.next:
temp = temp.next
tail2 = temp
# L1에서 잘라낼 구간의 앞(end1)과 뒤(start3) 찾기
count = 0
temp = L1
end1, start3 = None, None
while temp:
if count == a - 1:
end1 = temp
if count == b + 1:
start3 = temp
break
temp = temp.next
count += 1
# L2를 L1의 구간 사이에 연결
end1.next = head2
tail2.next = start3
return L1
L1 = [1,5,6,7,1,6,3,9,12]
L2 = [5,7,1,6]
a = 3
b = 6
print_list(solve(make_list(L1), make_list(L2), a, b))실행 결과
입력
[1,5,6,7,1,6,3,9,12], [5,7,1,6], 3, 6
출력
[1, 5, 6, 5, 7, 1, 6, 9, 12]
정리
이 문제는 연결 리스트의 포인터 재연결을 연습하기에 좋은 예제입니다. 시간 복잡도는 두 리스트를 한 번씩 순회하므로 O(m + n)이며, 새로운 노드를 생성하지 않으므로 공간 복잡도는 O(1)입니다. 인덱스 경계(a-1, b+1)를 정확히 처리하는 것이 실수 없이 구현하는 핵심 포인트입니다.