[Python] LeetCode - Merge Two Sorted List

Problem

 

Solving Process

linked list 의 merge 하는 방법이다.

이거는 먼저 linked list를 먼저 이해하는 것이 우선인 것같다.

 

list1 을 출력해보면,

ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}

와 같이 나오는 것을 확인할 수 있다.

즉, 현재 가르키고 있는 head 의 값인 val 와 다음을 가르키는 정보 next가 들어있는 것이다.

이를 사용하여, 

list1과 list2 중 하나가 소진 될 때 까지 돌면서 크기를 비교하며 새로운 linked list에 값을 넣다가

마지막에 남은 list 의 값을 넣어주는 것으로 끝내면 된다.

 

물론 새로운 linked list 에 값을 넣는 과정을 설명하자면

크기비교를 하고

작은 값을 새로운 linked list에 넣은 후

넣었던 리스트의 현재 head값을 next로 옮겨주는 작업을 반복 하면된다.

 

 

Solution

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        answer = ListNode()
        curr = answer
        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
        curr.next = list1 or list2
        return answer.next

마지막 curr.next = list1 or list2 는 둘 중 하나가 값이 있으면 값이 있는 것으로 나타나니 그 리스트의 값을 next로 넣어주기 위함이다.