[LeetCode 해석 및 풀이] 21. Merge Two Sorted Lists

LeetCode 문제 해석 및 풀이 방법
 

문제 21. Merge Two Sorted Lists(두개의 정렬된 연결리스트 합병)

바로가기
 

문제 설명

영문

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.
 

한글

두 개의 정렬된 연결리스트의 머리인 list1, list2가 주어집니다.
 
두 개의 리스트를 하나의 정렬된 리스트로 합치십시오. 리스트는 두 리스트의 노드들을 합쳐서 만들어야 합니다.
 
합쳐진 연결 리스트의 머리를 반환하세요.
 

제한조건

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

 

입출력 예

입력	출력
list1 = [1,2,4], list2 = [1,3,4]	[1,1,2,3,4,4]
list1 = [], list2 = []	[]
list1 = [], list2 = [0]	[0]

 
 

해답 및 해설

파이썬 (Python)

순회를 이용한 방법

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = now_node = ListNode()

        while list1 and list2:
            if list1.val <= list2.val:
                now_node.next = list1
                list1 = list1.next
            else:
                now_node.next = list2
                list2 = list2.next
            now_node = now_node.next

        if not list1:
            now_node.next = list2
        if not list2:
            now_node.next = list1

        return head.next

 2포인터 문제처럼 각각 리스트의 포인터를 하나씩 이동해가면서 풀어주면 되는 문제. 우선 가짜 head를 만든 후, 포인터에 있는 노드의 값이 작은 쪽부터 때어서 계속 붙여주고 포인터를 이동시킨다. 한쪽이 빈 리스트가 되면 나머지는 그냥 뒤에다가 붙여준다.
(마지막을 now_node.next = list1 or list2로 적은 풀이도 있었다)
 

재귀를 이용한 풀이

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1: return list2
        if not list2: return list1

        if list1.val <= list2.val:
            head = list1
            head.next = self.mergeTwoLists(list1.next, list2)
        else:
            head = list2
            head.next = self.mergeTwoLists(list1, list2.next)

        return head

재귀는 항상 즐겁다