LeetCode Top Interview 150) Merge Two Sorted Lists

Question

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

# 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]:

---

---

두 정수 링크드리스트 list1, list2의 헤더가 주어지고 두 리스트의 원소를 오름차순 정렬하여 합치면서 새로운 링크드리스트를 만들어 헤더를 반환하는 문제입니다.

제가 생각한 코드는 다음과 같습니다.

# 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]:
        if list1 == None and list2 == None:
            return None

        new_node =  ListNode()
        node = new_node
        while list1 != None or list2 != None:
            node = node.next if node.next != None else node

            val1 = list1.val if list1!=None else 101
            val2 = list2.val if list2!=None else 101

            if val1 < val2 :
                node.val = val1
                list1 = list1.next if list1 != None else None
            else:
                node.val = val2
                list2 = list2.next if list2 != None else None

            node.next = ListNode()

        node.next = None

        return new_node

• 두 노드가 모두 빈 예외상황을 처리합니다.
• 새로운 노드의 헤더 new_node를 정의하고 헤더는 따로두고 사용을 위해 node를 따로 선언합니다.
• 두 노드의 마지막까지 탐색하는동안 while문으로 반복합니다.
  • 반복문을 시작하며 다음 노드를 node로 가지고옵니다. 맨 처음엔 다음 노드가 없으므로 조건문을 통해 예외처리를 합니다.
  • 두 리스트 중 값중 작은 값을 현재 노드의 값으로 저장하고 저장한 값의 링크드리스트는 다음 노드로 이동합니다.
  • node의 다음 노드를 미리 생성해줍니다. 헤더 노드를 받은 채로 들어오기 때문에 새로운 반복문이 시작하기 전에 미리 선언하여 반복문의 흐름이 일치하게 만듭니다.
• 마지막까지 모든 원소를 확인하고 선언된 상태의 마지막 노드를 다시 None으로 초기화합니다.

---

이전 문제에서 알고리즘보다 마지막에 남는 불필요한 노드를 어떻게 제거할지 생각하는데 더 신경을 많이 썼다고 했었는데.. 덕분에 이번 문제는 비교적 쉽게 지나갔던것 같습니다.

이 문제 역시 링크드리스트의 개념과 클래스의 기본만 안다면 알고리즘 자체는 구현이 어렵지 않은 문제였습니다.

• 이 문제역시 근소한 차이로 백분율이 많이 바뀌므로 크게 신경쓰지 않아도 될 듯 합니다.