정렬된 두 개의 연결 리스트 L1과 L2가 주어졌을 때, 이 두 리스트에 공통으로 존재하는 원소들만 담고 있는 새로운 정렬된 연결 리스트를 만들어야 합니다.
예를 들어 입력이 L1 = [2, 4, 8], L2 = [3, 4, 8, 10]이라면, 두 리스트에 모두 포함된 값은 4와 8이므로 출력은 [4, 8]이 됩니다.
해결 접근 방식
두 리스트가 이미 정렬되어 있기 때문에, 각 리스트의 앞부분부터 동시에 순회하면서 값을 비교하는 투 포인터(two pointer) 기법으로 효율적으로 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 값이 0인 더미(dummy) 노드를 생성하여 head로 지정하고, cur 포인터도 head를 가리키도록 초기화합니다.
- l1과 l2가 모두 끝나지 않은 동안 아래 과정을 반복합니다.
- l1의 값이 l2의 값보다 작으면 → l1을 다음 노드로 이동시킵니다.
- l2의 값이 l1의 값보다 작으면 → l2를 다음 노드로 이동시킵니다.
- 두 값이 같으면 → cur.next에 해당 값을 가진 새 노드를 연결하고, l1과 l2를 각각 다음 노드로 이동시킨 뒤 cur도 한 칸 전진합니다.
- 반복이 끝나면 head.next를 반환합니다. 더미 노드를 제외한 실제 결과 리스트가 반환됩니다.
값이 작은 쪽 포인터만 앞으로 이동시키기 때문에, 두 값이 일치하는 순간에만 결과 리스트에 노드가 추가됩니다. 이 방식의 시간 복잡도는 O(n + m)이며, 추가 리스트 없이 결과만큼의 공간만 사용하므로 매우 효율적입니다.
구현 예제
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):
head = cur = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
l1 = l1.next
elif l2.val < l1.val:
l2 = l2.next
else:
cur.next = ListNode(l1.val)
l1 = l1.next
l2 = l2.next
cur = cur.next
return head.next
ob = Solution()
L1 = make_list([2, 4, 8])
L2 = make_list([3, 4, 8, 10])
print_list(ob.solve(L1, L2))입력
[2, 4, 8], [3, 4, 8, 10]
출력
[4, 8]