(leetcode 문제 풀이) Merge Two Sorted Lists

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: l1 = [], l2 = []
Output: []

Example 3:
Input: l1 = [], l2 = [0]
Output: [0]

Constraints:
1. The number of nodes in both lists is in the range [0, 50].
2. -100 <= Node.val <= 100
3. Both l1 and l2 are sorted in non-decreasing order.

# 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:
        head = ListNode(-1) # 결과 리스트 초기화
        cursor = head
        
        while l1 != None and l2 != None:
            if l1.val < l2.val:
                cursor.next = l1
                l1 = l1.next # 다음 노드를 가리키도록 업데이트
            else:
                cursor.next = l2
                l2 = l2.next
                
            cursor = cursor.next # 포인터를 다음 노드로 옮기기
        
        # while문 종료 조건 -> l1이 None이 되었거나 l2가 None이 됨
        if l1 != None: # l2가 None일 경우
            cursor.next = l1
        else: # l1이 None일 경우
            cursor.next = l2
           
        # l1과 l2가 모두 빈 linked list일 경우 head.next는 빈 리스트가 됨
        return head.next

해당 문제는 Linked List에 대한 개념이 있다면 크게 어렵지 않은 문제다.

먼저, 결과로 출력할 Linked List를 하나 선언하고 next를 통해 그 뒤에 노드를 연결해나가면 된다. 이때 l1과 l2의 노드값을 비교해서 더 작은 값의 노드를 선택하면 되고, 해당 노드의 포인터가 다음 노드를 가리키도록 한다.

cursor 역시 포인터가 다음 노드를 가리키도록 업데이트하면 기본적인 반복문은 완성된다.

while문을 빠져나오는 조건은 l1이 None이 되었거나 l2가 None이 된 상황이다. 둘 모두 None이라면 그대로 출력하면 되지만, 하나라도 남아있는 경우 남은 부분을 그대로 붙여준 후에 출력하면 된다.