[연결 리스트] 두 정렬 리스트의 병합

* leetcode 21. Merge Two Sorted Lists

 

Q. 정렬되어 있는 두 연결 리스트를 합쳐라

# 입력
1->2->4, 1->3->4

# 출력
1->1->2->3->4->4

---

풀이 1. 재귀 구조로 연결

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    # 작은 값이 왼쪽에 오게
    if (not l1) or (l2 and l1.val > l2.val):
        l1, l2 = l2, l1 
    
    # next는 그 다음 값이 엮이도록 재귀 호출
    if l1:
        l1.next = mergeTwoLists(l1.next, l2)
    
    return l1