LeetCode 21번 문제

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def my_solution(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 빈 연결 리스트의 경우
        if not l1 and not l2:
            return None
        if not l1:
            return l2
        if not l2:
            return l1

        # 연결 리스트의 머리와 현재 위치를 초기화
        merged_node = curr_node = None

        # 두 리스트 병합 수행
        while l1 and l2:
            if l1.val >= l2.val:
                if not curr_node:
                    merged_node = curr_node = ListNode(l2.val)
                else:
                    curr_node.next = ListNode(l2.val)
                    curr_node = curr_node.next
                l2 = l2.next
            else:
                if not curr_node:
                    merged_node = curr_node = ListNode(l1.val)
                else:
                    curr_node.next = ListNode(l1.val)
                    curr_node = curr_node.next
                l1 = l1.next

        # 연결 리스트에 요소가 남았다면 남은 요소를 모조리 연결
        if not l1:
            while l2:
                curr_node.next = ListNode(l2.val)
                curr_node = curr_node.next
                l2 = l2.next
        else:
            while l1:
                curr_node.next = ListNode(l1.val)
                curr_node = curr_node.next
                l1 = l1.next

        return merged_node

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def solution1(self, l1: ListNode, l2: ListNode) -> ListNode:
        # l1과 l2 값을 비교, 작은 값을 왼쪽(l1)으로 스왑
        if (not l1) or (l2 and (l1.val > l2.val)):
            l1, l2 = l2, l1
            
        # l1의 next를 재귀 호출
        # 최종적으로 모두 백트래킹으로 엮이면서 하나의 연결 리스트로 병합
        if l1:
            l1.next = self.solution1(l1.next, l2)
        return l1