Merge Two Sorted Lists

# 각각 정렬된 두개의 연결리스트를 가지고
# 정렬된 하나의 연결리스트를 리턴해라

# 일단 기준이 될 연결리스트를 임의로 지정함

# l2 를 지정하겠음

# 새롭게 정렬하려면 값의 크기를 비교해서 자신이 작으면 그대로 다음 요소를 비교하게 하고
# 자신이 크면 상대방과 바꿈

# 이것을 연결리스트를 이동하면서 끝까지 반복

# "연결리스트를 이동" 을 재귀함수로 구현함

# 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:

        if (not l2) or (l1 and l2.val > l1.val):
            temp = l2
            l2 = l1
            l1 = temp

        if l2:
            l2.next = self.mergeTwoLists(l2.next, l1)

        return l2

함수 호출

1>

L2: 1→3→4

L1: 1→2→4

L2.next? = 1→2→3→ 4→4→N

L2? = 1→1→2→3→ 4→4→N ( 최종리턴 )

2>

L2: 3→4

L1: 1→2→4

change

L2: 1→2→4

L1: 3→4

L2.next? = 2→3→ 4→4→N

L2? = 1→2→3→ 4→4→N

3>

L2: 2→4

L1: 3→4

L2.next? = 3→ 4→4→N

L2? = 2→3→ 4→4→N

4>

L2: 4→n

L1: 3→4

change

L2: 3→4

L1: 4→N

L2.next? = 4→4→N

L2? = 3→ 4→4→N

5>

L2: 4→N

L1: 4→N

L2.next? = 4→ N

L2? = 4→4→N

6>

L2 : N

L1 : 4→N

change ( L2 이 기준이니 L1 가 남아있으면 안됨 )

L2: 4→ N

L1 : N

L2.next? = N

L2? = 4→ N

7>

L2 : N

L1 : N

( L1,L2 끝까지 왔으니 리턴 )

return N

재귀함수로 끝까지 왔으니 다시 올라간다.