print('yongineer')

Leetcode - 21. Merge Two Sorted Lists

August 10, 2021

python

문제

정렬되어 있는 두 연결 리스트를 병합하고 정렬하여 반환하라

Example 1.

https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2.

Input: l1 = [], l2 = []
Output: []

Example 3.

Input: l1 = [], l2 = [0]
Output: [0]
ListNode{val: 0, next: None}
ListNode{val: 0, next: None}

나의 풀이

# 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]:
        rev = ListNode()
        res = rev

        while l1 and l2:
            if l1.val < l2.val:
                res.next = l1
                l1 = l1.next
            else:
                res.next = l2
                l2 = l2.next

            res = res.next

        res.next = l1 if l1 else l2

        return rev.next

https://yongineer.duckdns.org/python/leetcode_21_1.png

rev에 ListNode클래스 인스턴스를 생성해주고 이를 res가 참조한다. l1과 l2가 None이 될때가지 반복을 돌려주고 l1과 l2를 비교하여 l1이 작다면 res의 다음 노드(res.next)에 l1을 할당하고 l1을 다음 노드로 이동시켜 준다.

만약 l2가 작다면 rex의 다음 노드에 l2를 할당하고 l2를 다음 노드로 이동시켜준다. 비교 과정이 끝나면 res를 다음 노드로 이동 시켜 주고 이를 반복한다.

l1과 l2모두 끝 지점까지 도달하였으면 반복을 종료하고 res의 다음 노드에 l1또는 l2의 나머지를 연결 하고 res가 참조하고 있는 rev의 next를 리턴해준다.

풀이 : 재귀 구조로 연결

# 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]:
        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

먼저 l1의 None이 아니거나 l2가 None이 아니면서 l1의 값이 l2의 값보다 작을때 l1과 l2 변수를 스왑한다. 이후에 l1이 None이 아니라면서 l1의 next를 재귀호출하면서 다음번 연결 리스트가 계속 스왑될 수 있게 한다.

이렇게 스왑하면서 그 다음 값이 엮이도록 계속 재귀호출 하면 연결 리스트가 점점 하나로 병합된다. 마지막에는 l1이 None이 되면서 재귀가 끝나고 리턴을 시작한다.

연산자 우선순위

우선순위연산자설명
1()괄호
2f(args...)함수 호출
3x[index:index]슬라이싱
4x[index]배열
5x.attribute속성 참조
6**지수
7~x비트 연산 NOT
8+x, -x양수, 음수
9*, /, %곱, 나눗셈, 나머지
10+, -덧셈, 뺄셈
11<<, >>비트 연산 시프트
12&비트 연산 AND
13^비트 연산 XOR
14|비트 연산 OR
15in, not in, is, is not, <, ≤, >, ≥, <>, ≠, ==비교 연산
16not xBool 연산 NOT
17andBool 연산 AND
18orBool 연산 OR
19lambda람다 표현

변수 스왑

두 변수를 스왑하는 가장 일반적이고 널리 사용되는 방법은 임시 변수를 사용하는 방법이다.

temp = a
a = b
b = temp

이 방식은 거의 모든 언어에서 사용할 수 있는 가장 기본적인 방식이다. 그러나 Python에서는 다중 할당을 통해 이 변수 스왑이 가능하며 가독성 또한 좋아 별다른 이슈가 없는 한 이 방식으로 스왑하는게 가장 좋다.

a: int = 1
b: int = 2
a, b = b, a

숫자형인 경우 간단한 덧셈, 뺄셈을 통해 임시 변수 없이 스왑을 할 수 있는 방법이 있고 다음과 같이 가능하다.

x += y
y = x - y
x -= y

여기서 만약 입력값이 x=9, y=4라고 가정한다면 결과는 다음과 같다.

  1. x += y의 결과 x=13
  2. y = x -y의 결과 y=9
  3. x -= y의 결과 x=4
>>> x = 9
>>> y = 4
>>> x += y
>>> y = x-y
>>> x -= y
>>> x
4
>>> y
9

이 방식은 추가 공간을 필요로 하지 않는다는 점에서 공간 복잡도 또한 필요하지 않은 좋은 방법이나 숫자여야 하는 등의 제약사항으로 실용적인 면은 다소 부족하다. 다만 간혹 오프라인 인터뷰에서 이런 질문이 나오기도 하여 알아둘 필요는 있다.

Written by@Yongineer
Backend Developer

GitHubInstagram