leetcode/python/ 21. Merge Two Sorted Lists

Description

Merge Two Sorted Lists - LeetCode

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a 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.

---

Process

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.

 

첨에 이게 머지? 하고 멍 때리고 삽질했는데 그냥 간단한 링크드 리스트 구현 문제다.

 

---

Solution1: Time: 37 ms (72.13%), Space: 14 MB (20.93%) 

# 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]) -> ListNode:    
        if not list1 or not list2:
            return list1 or list2

        ans = None

        while list1 or list2:
            if not list1:
                cur = ans
                while cur.next:
                    cur = cur.next
                cur.next = list2
                return ans
            elif not list2:
                cur = ans
                while cur.next:
                    cur = cur.next
                cur.next = list1
                return ans
            if list1.val <= list2.val:
                if not ans:
                    ans = ListNode(val=list1.val, next=None)
                else:
                    cur = ans
                    while cur.next:
                        cur = cur.next
                    cur.next = ListNode(val=list1.val, next=None)
                list1 = list1.next
            else:
                if not ans:
                    ans = ListNode(val=list2.val, next=None)
                else:
                    cur = ans
                    while cur.next:
                        cur = cur.next
                    cur.next = ListNode(val=list2.val, next=None)
                list2 = list2.next
        return ans

 

1. list1 또는 list2가 빈 경우 바로 둘 중 존재하는 값을 반환해준다

 

2. 정답 초기화 (ans)

 

3. list1이나 list2가 있는 동안 계속 한다

 

3-1. list1이 없는 경우: 현재 ans의 마지막 노드의 next로 list2를 이어주고 반환한다

 

3-2. list2가 없는 경우: 현재 ans의 마지막노드의 next로 list1을 이어주고 반환한다

 

3-3. list1의 val이 list2의 val보다 작거나 같은 경우

3-3-1. ans가 비어 있다면 list1의 val로 새로운 노드를 생성해 할당해준다

3-3-2. ans가 있다면 마지막 노드를 찾아 next로 list1의 val로를 이어준다

3-3-3. list1의 next를 list1으로 할당한다

 

3-4. list1의 val이 list2의 val보다 큰 경우

3-4-1. ans가 비어 있다면 list2의 val로 새로운 노드를 생성해 할당해준다

3-4-2. ans가 있다면 마지막 노드를 찾아 next로 해당 list2의 val를 이어준다

3-4-3. list2의 next를 list2로 할당한다

 

4. 반복 종료 후 ans 반환

---

Solution1' (Refactor): Time: 36 ms (75.87%), Space: 13.9 MB (65.51%)

# 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]) -> ListNode:
        if not list1 or not list2:
            return list1 or list2
        
        def create_node(val):
            return ListNode(val=val, next=None)
        
        def add_node(node, val):
            new_node = create_node(val)
            node.next = new_node
            return new_node

        ans = None
        cur = None

        while list1 or list2:
            if not list1:
                cur.next = list2
                break
            elif not list2:
                cur.next = list1
                break
            elif list1.val <= list2.val:
                if not ans:
                    ans = create_node(list1.val)
                    cur = ans
                else:
                    cur = add_node(cur, list1.val)
                list1 = list1.next
            else:
                if not ans:
                    ans = create_node(list2.val)
                    cur = ans
                else:
                    cur = add_node(cur, list2.val)
                list2 = list2.next
        return ans

 

기존 코드에서 중복되는 부분을 추출하고, 매번 while문으로 연결된 노드의 마지막을 찾는 것이 아니라 cur에 저장해놓도록 리팩토링했다. 보기엔 훨씬 좋아보이는데 입력값이 크지 않아서인지 성능 차이는 크게 느껴지지 않는다.

 

---

Conclusion

머리에 힘줘서 예외를 먼저 생각하려고 한다. 계속 한번에 딱 구현까지 안 나오고 있기는 한데 일단 더 노력한다 빱빱