문제 링크
이미 정렬된 두 개의 연결리스트가 주어졌을 때 순서대로 두 연결리스트를 병합해라.
주어진 리스트가 이미 정렬되어 있기 때문에 L1과 L2의 요소를 하나씩 접근해 비교하면서 작은 요소를 output에 넣는다. L1, L2 중 한 리스트에만 요소가 존재한다면 남아있는 요소를 모두 output에 넣는다. 합병 정렬에서 맨 마지막 단계와 동일한 방법이다. 단계별 과정을 아래에 그려보았다.
1) 합병된 결과를 가리키는 ListNode형태의
dummy
를 하나 만든다.dummy
는 결과 리스트의 시작노드인 head를 가리킨다.
2) 파란색 포인터처럼 L1, L2 요소를 하나씩 접근해 값이 작은 요소를dummy
에 add한다.
3) L1, L2 중 하나만 존재하면 나머지 요소를 모두dummy
에 넣는다.
👉 결과적으로
dummy
는 결과 리스트의 시작노드인 head를 가리키고,tail
은 결과 리스트의 마지막노드를 가리킨다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# 순차적 방법
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
if l1:
tail.next = l1
elif l2:
tail.next = l2
return dummy.next
참고 : NeetCode