Merge Two Sorted Lists

https://leetcode.com/problems/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의 모든 원소는 head로 합쳐지며 curr을 통해 추가한다.
• while문을 돌면서 list1이 가리키는 값과 list2가 가리키는 값을 비교하고 더 작은 값을 curr에 추가한다.
  • list1, list2가 가리키는 값을 next로 이동시킨다.
• 추가했으므로 curr은 curr.next로 이동한다.
• while문은 두 배열중 하나가 none이 되면 종료되므로 각 배열이 존재한다면 curr.next에 이어준다.

Solution(Runtime: 45ms)

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = curr = ListNode()

        while list1 and list2:
            if list1.val < list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next
        
        if list1:
            curr.next = list1
        if list2:
            curr.next = list2
        
        return head.next

다른 사람의 재귀 방식 풀이이다. a에 합쳐지는 방식이며 b는 none이거나 크거나 같은 값을 가진다.

def mergeTwoLists(self, a, b):
    if not a or b and a.val > b.val:
        a, b = b, a
    if a:
        a.next = self.mergeTwoLists(a.next, b)
    return a