[leetcode][파이썬]Merge Two Sorted Lists #006

https://leetcode.com/problems/merge-two-sorted-lists/description/

 

 

 

---

 

 

 

 

오늘풀어본 문제는 " Merge Two Sorted Lists" 이다.

파라미터로 두 개의 싱글 링크드리스트가 주어진다. 간단히 말하면, 두 링크드리스트를 합쳐야한다(merge). 단, 정렬된 상태로 말이다(sorted).

 

 

 

 

 

풀이 #1 - Iteration

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode(-1)
        prev = head

        while list1 and list2:
            if list1.val >= list2.val:
                prev.next = list2
                list2 = list2.next
            else:
                prev.next = list1
                list1 = list1.next
            prev = prev.next

        prev.next = list1 if list1 is not None else list2
        return head.next

 

내가 고안한 방법은 각 링크드리스트를 순환하면서 각 링크드리스트의 노드(node)의 값(val)끼리 비교해 작거나 같은 값을 가진 노드를 어느 한 노드가 더이상  이동할 수 없을 때 까지 연결 및 병합 시킨다. 여기서 작거나 값을 값이라는 조건은 위 문제에서 오름차순(acsending-order) 정렬이었다.

 

 

 

 

풀이순서

1. 변수 head에 더미 노드(dummy node)로 설정

2. 변수 prev = head를 할당하여 앞으로 병합될 리스트 위치 추척 

  - 또한, head를 유지하는 목적도 존재

3. while문에서 list1 또는 list2 둘 중 하나가 끝날 때가지 반복하도록 함

  3-1. list1의 값과 list2의 값을 비교해 작거나 같은 값을 가진 노드부터 병합

  3-2. 병합 후, 다음 반복(loop) 후 새로운 값을 병합을 위해 prev.next를 재할당

4. while문 종료 후, 끝나지 않은 남은 링크드리스트 변수를 연결 및 병합

5.  head의 next 를 리턴하여 병합된 값을 반환

 

 

다른 풀이: Recursion

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

 

링크드리스트와 재귀함수를 이용한 방법이다. 

 

 

 

알게된 점

- 처음 초기화하는 부분에서 "변수 prev = head를 할당하여 앞으로 병합될 리스트 위치 추적과 head를 유지하는 목적도 존재" 라고 했다. 이 부분이 헷갈렸다. 왜 굳이 두 번 할당할 필요가 있을까 해서 말이다. 이번 기회를 통해 그 동안 헷갈렷던 부분이 해소가 되었다.