코딩 테스트 대비! 파이썬으로 "두 정렬 리스트의 병합" 문제 풀이

파이썬으로 "두 정렬 리스트의 병합" 문제 풀이


문제 설명

정렬된 연결 리스트 l1과 l2가 주어졌을 때, 이 두 리스트를 병합하여 정렬된 새 연결 리스트를 반환하는 프로그램을 작성하세요.


제약 조건

- 두 리스트의 노드 수는 0 이상 50 이하입니다.
- -1,000 ≤ Node.val ≤ 1,000


예시 입출력

- l1 = [1,2,4], l2 = [1,3,4] → [1,1,2,3,4,4]
- l1 = [], l2 = [] → []
- l1 = [], l2 = [0] → [0]


솔루션 코드

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_sorted_lists(l1, l2):
    dummy = ListNode()  # 더미 노드
    curr = dummy  # 현재 노드 포인터
    
    # 두 리스트를 병합
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next

    # 나머지 노드 연결
    if l1:
        curr.next = l1
    elif l2:
        curr.next = l2
        
    return dummy.next  # 더미 노드 다음 노드부터 리턴

# 테스트
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
merged = merge_sorted_lists(l1, l2)

while merged:
    print(merged.val, end=" ")
    merged = merged.next  # 1 1 2 3 4 4

코드 설명

1. 연결 리스트 노드 클래스 ListNode를 정의합니다.
2. 병합된 리스트를 만들기 위해 더미 노드를 생성하고, curr 포인터를 사용합니다.
3. l1과 l2를 순회하면서 값이 작은 노드를 curr.next에 연결합니다.
4. l1과 l2 중 하나라도 끝나면 나머지 노드를 curr.next에 연결합니다.
5. 더미 노드의 다음 노드부터 리턴합니다.

이 풀이의 시간 복잡도는 O(m+n)이며, 공간 복잡도는 새로운 리스트를 만들어야 하므로 O(m+n)입니다. (m, n은 각 리스트의 길이)

이번 문제에서는 연결 리스트의 병합과 정렬을 다룹니다. 두 정렬 리스트를 하나씩 비교하면서 작은 값부터 새 리스트에 연결하는 방식으로 해결했습니다. 코딩 테스트에서 연결 리스트 문제가 자주 출제되므로 익숙해질 필요가 있습니다.