문제 개요
두 개의 연결 리스트 l1과 l2가 주어졌을 때, l1부터 시작하여 두 리스트의 노드를 번갈아 삽입(interleaving)해 하나의 연결 리스트를 만드는 문제입니다. 어느 한쪽 리스트에 노드가 남아 있으면, 남은 노드들은 결과 리스트의 끝에 그대로 이어 붙입니다.
예를 들어 입력이 l1 = [5,4,6,3,4,7], l2 = [8,6,9]라면, 두 리스트의 요소가 번갈아 배치된 [5,8,4,6,6,9,3,4,7]이 출력됩니다.
해결 접근 방법
핵심 아이디어는 포인터를 이용해 l2의 노드를 하나씩 꺼내 l1의 노드 사이사이에 끼워 넣는 것입니다. 알고리즘은 다음과 같이 진행됩니다.
결과 탐색용 포인터
ans를 l1으로 초기화합니다.l2가 비어 있지 않은 동안 아래 과정을 반복합니다.
ans가 null이 아니라면:ans의 다음 노드가 존재할 경우, l2의 값을 가진 새 노드를 만들어ans와ans.next사이에 삽입합니다. 이후ans는 새 노드의 다음 노드로,l2는 자신의 다음 노드로 각각 한 칸씩 이동합니다.ans가 마지막 노드인 경우,ans.next에 남은 l2 전체를 연결한 뒤 반복을 종료합니다.
ans가 null이라면(l1이 비어 있는 경우), l2를 그대로 반환합니다.
반복이 모두 끝나면 l1을 반환합니다.
이 방식은 기존 리스트의 링크 구조만 조작하면서 순서대로 삽입하기 때문에, 로직이 단순하고 각 노드를 한 번씩만 처리한다는 장점이 있습니다.
구현 예제
아래는 위 알고리즘을 파이썬으로 구현한 전체 코드입니다.
Source Code (Python):
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, l1, l2):
ans = l1
while l2:
if ans:
if ans.next is not None:
newnode = ListNode(l2.val)
newnode.next = ans.next
ans.next = newnode
ans = newnode.next
l2 = l2.next
else:
ans.next = l2
break
else:
return l2
return l1
ob = Solution()
l1 = make_list([5, 4, 6, 3, 4, 7])
l2 = make_list([8, 6, 9])
res = ob.solve(l1, l2)
print_list(res)
실행 결과
입력
[5,4,6,3,4,7],[8,6,9]
출력
[5, 8, 4, 6, 6, 9, 3, 4, 7]
복잡도 분석
두 리스트의 길이를 각각 n, m이라 할 때, 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n + m)입니다. l2의 값만큼 새 노드를 생성해 삽입하므로 추가 공간 복잡도는 O(m)입니다. 리스트 길이가 서로 달라도 자동으로 처리되며, 짧은 쪽이 소진되면 긴 쪽의 나머지 노드가 그대로 뒤에 붙습니다.