14. Merge Two Sorted Lists

🎯 leetcode - 21. Merge Two Sorted Lists

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 14번 문제

📌 날짜

2020.01.24

📌 시도 횟수

FAILED / 문제 조건 제대로 확인 후 다시 풂

💡 Code

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1

        result = []

        while l1:
            result.append(l1.val)
            l1 = l1.next
        while l2:
            result.append(l2.val)
            l2 = l2.next
            
        result.sort()
        
        head = curr = ListNode(0)
        for value in result:
            curr.next = ListNode(value)
            curr = curr.next
            
        return head.next

💡 문제 해결 방법

- 각각 list1, list2로 옮긴 다음에 sorted(list1+list2)로 정렬하고,
- 정렬된 list를 다시 연결 리스트로 만든 후 리턴한다.

💡 새롭게 알게 된 점

- list를 linked list로 변환 후 반환까지 하는 방법에 대해 알게 됨

>> (list)리스트를 linked list로 변환하기
head = curr = ListNode(0) # dummy 값임
for value in list:
    curr.next = ListNode(value)
    curr = curr.next
return head.next # dummy 값 건너뛰기

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 문제 조건 중에 "이미 정렬되어 있는"을 못봤다!!!!😥
- 그래서 따로따로 list로 받고 sorted(list1 + list2)를 해준 다음에 다시 연결
리스트로 만드는 방법을 생각했는데... 잘 안됐다.

---

😉 다른 풀이

📌 하나. 값을 비교해서 차례대로 넣기

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = sort_list = ListNode()

        while (l1 and l2):
            if (l1.val < l2.val):
                sort_list.next = l1
                l1 = l1.next
            else:
                sort_list.next = l2
                l2 = l2.next
            sort_list = sort_list.next
        
        sort_list.next = l1 or l2
        return head.next

💡 새롭게 알게 된 점

- 이때도 맨 첫번째 값을 dummy 값으로 지정해 head.next부터 return 해주었다.

---

📌 둘. 재귀로 연결👏

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if (not l1) or (l2 and (l1.val > l2.val)):
            l1, l2 = l2, l1
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

💡 새롭게 알게 된 점

- 어렵다

🌵재귀로 푸는 방법 이해하기🌵