[LeetCode] Merge Two Sorted Lists

Problem

• list1, list2 두개의 정렬된 링크드 리스트의 head가 있다. 하나의 정렬된 리스트에서 두 개의 리스트들을 병합하라. 리스트는 처음 두 목록의 노드를 함께 연결해서 만들어야하며 병합된 링크드 리스트의 헤드를 반환하라.

• There is two sorted linked lists, list1 and list 2. Merge two lists into one sorted list. The list should be made by splicing together the nodes of first two lists.

• 예:
  

Code

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()
        while list1 and list2: 
            if list1.val < list2.val:
                cur.next = list1
                cur = cur.next
                list1 = list1.next
            else: 
                cur.next = list2
                cur = cur.next 
                list2 = list2.next
        if list1 or list2:
            cur.next = list1 if list1 else list2 

        return dummy.next

Explanation

반복문을 돌면서 현재 노드를 가리킬 변수 cur과 병합된 리스트의 head를 가리킬 dummy 노드를 선언한다.

list1과 list2의 원소가 존재할 때까지 반복문을 돌며, list1의 원소가 list2의 원소보다 작을 때, 현재 원소의 다음원소를 list1로 지정하고, 현재 커서를 현재 커서의 다음 원소로 지정한다. list1은 list1의 다음원소를 가리키게 한다.

그 밖의 경우 (list1의 원소가 list2의 원소보다 클 때), 현재 원소의 다음원소를 list2로 지정하고,
현재 커서를 현재 커서의 다음 원소로 지정한다. list2는 list2의 다음원소를 가리키게 한다.
list1과 list2 중 하나라도 원소가 남아있을 경우, 현재 원소의 다음원소를 list1 또는 list2로 지정한다.

병합된 리스트의 head를 가리키는 dummy.next를 리턴한다.