[LeetCode] 21. Merge Two Sorted Lists

문제 링크 : https://leetcode.com/problems/merge-two-sorted-lists/

Merge Two Sorted Lists - LeetCode

 

이 문제는 정렬된 두 개의 linked list를 merge하여 정렬된 linked list를 반환하는 문제이다.

 

풀이방법

두 리스트가 이미 정렬이 되어있기 때문에 merge sort와 같은 방법으로 풀었다.

두 리스트 중 작은 쪽을 merge_list에 복사하는 작업을 반복하여 merge_list를 반환하였다.

l1, l2 리스트의 연결 자체를 바꾸는 방법도 가능할 것 같은데 새로운 merge_list를 만드는 쪽이 더 쉽고 직관적이어서 다음과 같이 풀이하였다.

# Definition for singly-linked list.
# 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:
        # 둘 다 빈 리스트일 때
        if not l1 and not l2:
            return None
        merge_list = ListNode()
        # curr = 현재 List 위치
        curr = merge_list
        while l1 or l2:
            if not l1:
                curr.val = l2.val
                l2 = l2.next
            elif not l2:
                curr.val = l1.val
                l1 = l1.next
            elif l1.val > l2.val:
                curr.val = l2.val
                l2 = l2.next
            elif l1.val <= l2.val:
                curr.val = l1.val
                l1 = l1.next
            if l1 or l2:
                curr.next = ListNode()
                curr = curr.next
        return merge_list