21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/description/
연결리스트에 대한 문제다.

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.

 

Example 1:


Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:

Input: list1 = [], list2 = []
Output: []
Example 3:

Input: list1 = [], list2 = [0]
Output: [0]
 

Constraints:

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.

연결리스트란 데이터 요소들이 노드(Node)라고 불리는 객체로 연결되어 있는 자료 구조다.
각 노드는 데이터와 다음 노드를 가리키는 포인터(또는 링크)로 구성되어 있다.
연결 리스트는 배열과 달리 메모리에서 연속적으로 배치되지 않으며, 각 노드들이 포인터를 사용하여 서로 연결되어 있는 형태로 데이터를 저장한다.

class Solution:
  def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    if not list1 or not list2:
      return list1 if list1 else list2
    if list1.val > list2.val:
      list1, list2 = list2, list1
    list1.next = self.mergeTwoLists(list1.next, list2)
    return list1

리스트가 비었는지 확인한다.
하나라도 비어있으면 비어있지 않은 리스트를 리턴한다.
둘 다 비어있으면 걍 빈 리스트 리턴.

그리고 첫번째 노드값을 비교하여 작은 것을 먼저 오게 한다.

mergeTwoLists() 함수는 두 개의 정렬된 연결 리스트를 합병하여 하나의 정렬된 연결 리스트를 반환한다.
list1의 첫번째 노드를 제외한 부분에 대해 재귀적으로 호출하여 나머지 노드들을 합병한다.