파이썬 알고리즘 인터뷰 - 14. 두 정렬 리스트의 병합

 

<--- 리트코드 21. Merge Two Sorted Lists --->

# 문제: 정렬되어 있는 두 연결 리스트를 연결하라.

 

입력

1->2->4, 1->3->4

출력

1->1->2->3->4->4

 

 

#풀이: 재귀 구조로 연결

from typing import List
 
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = None
 
def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    if (not l1) or (l2 and l1.val > l2.val):
        l1, l2 = l2, l1
 
    if l1:
        l1.next = merge_two_lists(l1.next, l2)
    return l1
 
list1 = ListNode(1)
list2 = ListNode(2)
list3 = ListNode(4)
head1 = list1
list1.next = list2
list2.next = list3
 
list4 = ListNode(1)
list5 = ListNode(3)
list6 = ListNode(4)
head2 = list4
list4.next = list5
list5.next = list6
 
head = merge_two_lists(head1, head2)
while head:
  print(head.val, end="")
  if head.next:
    print("->", end="")
  head = head.next