Node로 표현되는 List 다루기

                                    💡 min으로 비교하면서 넣기

min 값을 전체 고정
매번 각 list를 확인하면서 min값을 가진 list만 merged에 넣기 이후 next로 이동
min값이 아닌 케이스는 그대로 두기

생각해 볼 수 있는 case는 3개
list1 = 1 2 3
list2 = 1 2 3

1 2 3
2 3 4

1 2 3
4 5 6

크게 이런 식이다.

🤔 로직 정리
1. list1 is not None, list2 is not None인지 확인한다.
>>> a. 둘다 None이다 -> 전체 roof 종료
>>> b. 하나만 None이다 -> 나머지만 계산하면된다.
>>> c. 둘다 None이 아니다.

# c. 둘다 None이 아니다.
2. list1.val == list2.val인지 확인한다.
>>> 같다 -> merged에 두 개의 같은 val newNode를 넣는다.
>>> 2.1. list1.va1 > list2.val이다.
>>> 2.2. list1.val < list2.val이다.

2.1. list1.val > list2.val
>>> list2.val을 merged에 넣는다.
>>> list2 = list2.next

2.2. list1.val < list2.val
>>> list1.val을 merged에 넣는다.
>>> list1 = list1.next

# b 하나만 None이다
list1이 None 인 경우 -> list1은 이미 merged로 모두 통합되었다고 볼 수 있다.
list2만 계속해서 넣고 옮겨준다.

                                    1. height balanced를 알아보려면 좌/우 노드의 높이 차이가 1이하 여야 한다.

                                    # Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        merged = []

        while 1:
            if list1 == None and list2 == None:
                break

            if list1 is None and list2 is not None:
                # list1 is all merged, only merge list 2 !!

                merged.append(list2.val)
                list2 = list2.next

                continue
            if list1 is not None and list2 is None:
                # list2 is all merged, only merge list 1 !!

                merged.append(list1.val)
                list1 = list1.next

                continue

            # both are not none...
            if list1.val == list2.val:
                value = list1.val
                merged.append(value)
                merged.append(value)

                list1 = list1.next
                list2 = list2.next

            elif list1.val > list2.val:
                merged.append(list2.val)
                list2 = list2.next

            elif list1.val < list2.val:
                merged.append(list1.val)
                list1 = list1.next

        if merged:
            head = ListNode(merged[0])
            tmp = head

            for i in range(1, len(merged)):
                tmp.next = ListNode(merged[i])
                tmp = tmp.next
        else:
            head = None

        return head

                                    class Solution(object):
    def mergeTwoLists(self, list1, list2):
        head = ListNode()
        current = head
        while list1 and list2:
            if list1.val > list2.val:
                current.next = list2
                list2 = list2.next
            else:
                current.next = list1
                list1 = list1.next
            current = current.next

        # not none added
        current.next = list1 or list2

        return head.next

                                    # None 출력 = []

# head 저장하려면? 🔑 여기서 시간 많이 먹음
head = ListNode()
tmp = head 해주고
tmp를 next이동 시켜서 붙여주면 된다.
head를 직접 움직이면 head가 끝지점 이동시 None이 됨.

# slicing
list1 = [1, 2, 3] 이라고 가정
list1 = list1.next
list1 = [2, 3]이다 .

# node = list1 or list2

"X = a or b"는 파이썬에서
"X = a if a else b"의 간단한 표현을 사용하고,
 true와 false를 비교하는 데 쓰임을 발견

a가 참이면 b를 보지 않고 X = a가됨
a가 거짓이면 b를 확인하고 참인 경우 x = b
둘다 거짓이면 None = list2의 값(None이기에 false가 되므로)