사용 언어: python 3.9.5

❓ Problem

문제 설명

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

🚩 Solution

시도 01)

1. 접근법

1. 각 연결 리스트마다 포인터를 하나씩 가진다.

   예시) l1의 포인터는 l1_head, l2의 포인터는 l2_head

2. 포인터의 값들을 비교하면서 더 작은 노드를 answer에 삽입한다.

   1. 처음 주소가 같은 fixed, ptr 변수
   2. ptr이 새로운 노드의 주소를 매번 따라가면서 새로운 노드를 추가한다.
   3. fixed는 첫번째 노드 주소를 계속 가리키고 있다.

3. fixed의 다음 노드부터 원소가 저장되었으므로, fixed.next를 반환한다.

2. 코드

# 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, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        l1_head = l1
        l2_head = l2        
        fixed = ptr = ListNode()
        while l1_head and l2_head:
            if l1_head.val < l2_head.val:
                ptr.next = ListNode(l1_head.val)
                ptr = ptr.next
                l1_head = l1_head.next
                
            elif l1_head.val > l2_head.val:
                ptr.next = ListNode(l2_head.val)
                ptr = ptr.next
                l2_head = l2_head.next

            else:
                ptr.next = ListNode(l1_head.val)
                ptr = ptr.next
                ptr.next = ListNode(l2_head.val)
                ptr = ptr.next
                l1_head, l2_head = l1_head.next, l2_head.next

            
        while l1_head:
            ptr.next = ListNode(l1_head.val)
            ptr = ptr.next
            l1_head = l1_head.next
        while l2_head:
            ptr.next = ListNode(l2_head.val)
            ptr = ptr.next
            l2_head = l2_head.next
            
        return fixed.next  

3. 시간복잡도

$O(n)$

4. 결과

성공

5. 소요 시간

1시간 이상

📕 피드백

1. 검색한 내용

파이썬 얕은 복사와 깊은 복사에 대해 공부했다.
-> 파이썬 얕은 복사와 깊은 복사 정리한 내용

2. 실수

3. 발전 방향 (개선/추가사항)

4. 다른 사람 풀이

풀이1)

• 링크

• 접근법

• 코드

• 배울 점