LeetCode 21(Merge Two Sorted Lists, Python)

1. 문제 링크

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

Merge Two Sorted Lists - LeetCode

2. 문제 설명

• linked list 두 개가 주어졌을 때 하나의 linked list로 (오름차순으로) 병합하여 반환하는 문제
• 예시) head1=[1,2,4], head2=[1,3,4] 이면 [1,1,2,3,4,4]을 반환. 단, 평소 list가 아님에 유의. 

3. 처음 풀이 

• 논리는 간단, head1, head2 제일 앞의 노드의 값을 비교해서 작은 노드를 우리가 만든 노드의 다음 노드로 이어 붙이는 것을 반복
• 한쪽 노드가 모두 사용되면 남은 노드를 이어 붙임
• 헷갈리는 부분은 논리가 아니라 linked list의 구조나 가변 객체에 대한 부분, 이는 아래에 따로 정리

class Solution:
    def mergeTwoLists(self, head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
        result=ListNode(0)
        head3=result #작업용 head3와 반환용 result
        while head1 or head2:
            if head1 ==None: #head1이 끝난 경우
                head3.next=head2
                head2=head2.next
            elif head2 == None: #head2가 끝난 경우
                head3.next=head1
                head1=head1.next
            elif head1.val<=head2.val: #오름차순 위해 작은 값 head1 가져오기
                head3.next=head1 #다음 node 지정
                head1=head1.next #head1 한칸씩 당기기
            else: #오름차순 위해 작은 값 head2 가져오기
                head3.next=head2
                head2=head2.next
            head3=head3.next #head3 한칸씩 당겨서 head3가 계속 끝을 가르키도록 갱신
    
        return result.next

4. 일반적인 풀이 

• 큰 차이 없지만 보통 제일 많이 쓰는 모양

# 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]:
        curr = head = ListNode()

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

        if list1:
            curr.next = list1
        else:
            curr.next = list2

        return head.next

5. 배운 점 

• 가변 객체(mutable), 불변 객체(immutable)
  • 가변객체(mutable) : list, set, dict
  • 불변객체(immutable) : int, float, bool, tuple, string, unicode
  • linked list가 dict로 정의되어 있기 때문에 위 처음 풀이의 코드에서 head3를 바꾸는게 result에 줄줄이 반영됨
  • 차이를 살펴볼수 있는 코드

#불변객체(immutable)
a=1
b=a
a=2
print(b) #1 : a를 바꾸어도 b에 할당된 1은 바뀌지 않음


#가변객체(mutable)
a=[1,2,3,4]
b=a
a[0]=100
print(b) #[100,2,3,4] : a[0]을 바꾸면 b[0]도 바뀜

 

• 연결 리스트(Linked List)란

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
          self.val = val
          self.next = next

• 자료 구조의 하나로 데이터 하나(노드 Node)에 데이터 값(data field)과 그 다음 자료 위치(link field)를 저장
• 즉 비엔나 소시지처럼 줄줄이 엮인 구조
• 1번부터 10번까지 출석부를 생각해보면
  • 일반적인 배열(array) : 1번, 2번, 3번, …, 10번
  • 연결 리스트(linked list) : 1번 다음 2번, 2번 다음 3번, … 9번 다음 10번
• 장점 : 자료의 추가나 삭제가 쉽다. 2번을 삭제할 때
  • 배열 : 3번을 한 칸 앞으로, 4번도 한 칸 앞으로, … , 10번도 한 칸 앞으로
  • 연결 리스트 : 1번 다음 3번으로 수정. 끝
• 단점 : 탐색, 접근이 어렵다. 3번에 접근하려면
  • 배열 : 3번째 나와
  • 연결 리스트 : 1번 다음 2번, 2번 다음 3번 그래 3번 나와