[연결 리스트] 두 정렬 리스트의 병합

14번 pg.213

21 | Merge Two Sorted Lists
https://leetcode.com/problems/merge-two-sorted-lists/description/

 

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.

 

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

 

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.

 

 

작성 코드 (30분)

 

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        answer = Listnode(None)
        print(answer)
        while list1 and list2:
            if list1.val <= list2.val:
                answer.next = list1.val

 

• 연결 리스트 오랜만이라 다 까먹음...
• answer 이라는 빈 ListNode를 만든 후 list1과 list2의 첫 번째 val 값을 비교해서 작은 값을 붙이려고 했음
• 시간 부족 실패

 

 

이상 코드

 

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if (not l1) or (l2 and l1.val > l2.val):
            l1, l2 = l2, l1
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

 

• 재귀 형식
• or 보다 and 가 먼저 실행 ! if 문의 괄호를 제거해도 동일한 우선 순위로 실행됨
• 별도의 변수를 만들지 않고 l1 배열의 next 값을 바꿔가며 진행
• 스왑 방식 - 파이썬에서는 다중 할당을 지원함, 임시 저장 공간 변수를 만들어 스왑을 진행하는 것과 다중 할당을 통해 스왑을 진행하는 것에 큰 시간 차이가 없음