LeetCode [21]: Merge Two Sorted Lists

📌 LeetCode [21]: Merge Two Sorted Lists

🔗 문제 링크

---

문제 설명 📄

두 개의 정렬된 단일 연결 리스트 list1과 list2가 주어졌을 때, 두 리스트를 병합하여 정렬된 단일 연결 리스트로 반환하는 문제입니다.
새로운 리스트는 두 리스트의 노드를 재사용하여 구성해야 합니다.

---

문제 접근 방식 📋

1. 더미 노드 사용:
   • 병합 결과를 저장할 새로운 연결 리스트의 시작점을 잡기 위해 더미 노드(answer)를 생성합니다.
   • 현재 위치를 추적하기 위해 current 포인터를 사용합니다.
2. 리스트 병합:
   • 두 리스트를 순회하며, list1.val과 list2.val을 비교합니다.
   • 작은 값을 가진 노드를 결과 리스트에 추가하고, 해당 리스트를 다음 노드로 이동시킵니다.
3. 잔여 노드 처리:
   • 두 리스트 중 하나가 먼저 끝나면, 나머지 노드를 결과 리스트에 연결합니다.
4. 결과 반환:
   • 더미 노드의 다음 노드(answer.next)가 병합된 리스트의 시작점이므로 이를 반환합니다.

---

Solution 💻

# 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]:
        answer = ListNode() 
        current = answer    

        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next


        current.next = list1 if list1 else list2

        return answer.next  

---

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(m + n)
  • m은 list1의 길이, n은 list2의 길이. 두 리스트를 순회하면서 병합.
• 공간 복잡도: O(1)
  • 추가 메모리 없이 기존 노드를 재사용.

---