[파이썬 알고리즘] 두 정렬 리스트의 병합

-입력

1 -> 2 > 4     ,    1 -> 3 -> 4

-출력

1 -> 1 -> 2 -> 3 -> 4 -> 4

 

생각해본것

1) 두 연결 리스트는 정렬 돼있다. 흠 .. 그런 sorted 함수는 필요 x

2) 두 노드를 비교해서 작은 값부터 순서대로 넣어주면 되겠구나.

3) 그러면 어떻게 두 노드를 가지고 와서 비교를 할까? 

4) l1.val < l2.val 로 비교를 해보자

5) 작으면 넣어주고 크면 뒤로 빼주자.

 

근데.. 이렇게 생각을 했는데 구현을 하기까지의 과정이 안되더라구요

그래서 책에 있는 걸 봤어요..

코드를 봤는데 복잡하게 보이는 코드가 보기가 싫더라구요

구글링을 해봐서 

https://www.google.com/search?q=21.+merge+two+sorted+lists+py&oq=&aqs=chrome.7.35i39i362l8.30358190j0j15&sourceid=chrome&ie=UTF-8#kpvalbx=_M2F_YoI8kIP4BsmbkKgM16 

21. merge two sorted lists py - Google 검색

이분 영상껄 보는데 진짜 완전 쉬운겁니다!

dummy 개념을 이용하셨는데 아주 좋았습니다.

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

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        tail = dummy

        while l1 and l2:
            # l1과 l2가 not null
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next

            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
            #꼬리 포인터 업데이트

            if l1:
                tail.next = l1
            elif l2:
                tail.next = l2
            #마지막 l1과 l2 둘중 하나가 null이면 
            #null이 아닌값을 넣어줌

            return dummy.next