[LeetCode] 21. Merge_Two_Sorted_Lists (Easy) 2023/5/5

문제 제목	정답률	난이도
21. Merge-Two-Sorted-Lists	62.6%	Easy

Merge Two Sorted Lists - LeetCode

 

문제요약

정렬되어 있는 두 개의 연결리스트를 하나의 정렬된 연결리스트로 병합하라

조건 1) 두 개의 정렬된 연결리스트가 입력으로 주어진다

조건 2) 각 연결리스트의 길이는 0 이상 50 이하이다

조건 3) 합쳐진 하나의 정렬된 연결리스트의 헤더를 반환해야 한다

 

 

생각했던 풀이 1 : 두 개의 포인터를 이용해 풀이 (59ms)

생각했던 풀이 2 : 재귀함수를 이용한 풀이(55ms)

 

 

풀이 1

두개의 포인터를 이용한 풀이

 

Step1. 예외처리 -> 각 연결리스트 길이가 0인 경우

 

Step2. 첫 노드의 값이 더 작은 연결리스트를 기준으로 병합

기준 연결리스트의 첫 노드를 prev, 두 번째 노드를 pointer1 포인터로 나머지 연결리스트의 첫 노드를 pointer2 포인터로 가리킨다.

• pointer1.val>=pointer2.val 이면 prev와 pointer1 사이에 pointer2가 가리키는 노드를 삽입
• 그렇지 않다면 pointer1을 한 칸 전진

 

Step3. 나머지 연결리스트 중 판단되지 않은 노드가 있다면 그대로 기준 연결리스트 뒷부분에 병합

 

 

Step 2 과정을 그림으로 살펴보자.

다음과 같이 기준 연결리스트와, 나머지 연결리스트가 주어졌을 때,

pointer1 값과 pointer2 값을 비교해서

• pointer1 >=  pointer2 이면

• pointer1 < pointer2 이면

 

 

구현

# 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]:
        # Step 1 
        if list1==None:
            return list2
        if list2==None:
            return list1
		
        # Step 2
        result=None
        if list1.val<=list2.val:
            result=list1
            prev, pointer1=list1, list1.next
            pointer2=list2
        else:
            result=list2
            prev, pointer1=list2, list2.next
            pointer2=list1

        # 첫번째 리스트의 끝 숫자가 더 큼
        while pointer1!=None and pointer2!=None:
            if pointer1.val>=pointer2.val: #pointer1 앞에 연결
                prev.next, pointer2=pointer2, pointer2.next
                prev=prev.next
                prev.next=pointer1
            else:
                prev, pointer1=prev.next, pointer1.next
        # Step 3
        if pointer2!=None:
            prev.next=pointer2
        
        return result