[Leetcode] #21. Merge Two Sorted Lists

문제 :

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into 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.

 

두개의 정렬된 연결 리스트가 주어지고, 이 두개의 연결리스트를 오름차순으로된 하나의 연결 리스트로 합쳐야 한다.

 

- 처음 든 생각 :

 

1. 첫번째 인자로 주어진 첫번째 연결 리스트의 head부터 시작한다. head의 .next는 head보다는 큰 값일 것이다(이미 정렬된 연결 리스트이므로). 그러면 첫번째 리스트의 .next를 확인하는것 보단, 두번째 인자로 주어진 두번째 연결 리스트의 head와 첫번째 head와 비교한다. 여기서 더 작은값을 결과 리스트에 추가한다(두개의 값이 같다면, 둘 다 추가해 준다. 위의 예시처럼, 두 연결 리스트의 head가 모두 1이라면, 결과 리스트에 두개의 '1' 노드를 더해준다.)  

 

2. 두번째 노드도 같은 로직을 적용시킨다. 각 연결 리스트의 2번째 노드인 '2', '3'을 각각 비교해 더 작은 값을 결과 리스트에 먼저 더해준다. 하지만 여기서 무턱대고 3을 2 다음에 넣으면 안 된다. 1번에서는 두 노드의 값이 같기 때문에 한번에 두 노드를 결과 리스트에 저장했다면, 이번에는 값이 다르기 때문에 두 노드를 다 넣으면 안된다. 예를 들어보자. 첫번째 연결 리스트(1->2->3)와  두번째(1->4->5)가 있을때, 위의 로직을 따르면 (1->1->2->4-> ... ) 이렇게 될 것이다. 그렇지만 첫번째 연결 리스트의 다음 값은 3이고, 3은 4보다 작으므로 (1->1->2->3->4) 가 되어야 한다. 즉, "노드의 값이 같을 때에만 결과 리스트에 동시에 노드를 넣어주고, 그렇지 않다면, 두 노드를 비교해 두 노드중 작은 값만 결과 리스트에 넣어준다." 이때, 이미 값을 넣은 연결 리스트의 head만 .next를 통해 업데이트를 해 주고, 들어가지 않은, 즉 이번 예시에서 두번째 노드는 .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]:
         dummy = ListNode()
         curr = dummy
        while list1 and list2:               
            if list1.val < list2.val:
                curr.next = list1
                list1, curr = list1.next, list1
            else:
                curr.next = list2
                list2, curr = list2.next, list2
                
        if list1 or list2:
            curr.next = list1 if list1 else list2
            
        return dummy.next

 

위의 코드를 살펴보자. 먼저, 

• dummy = ListNode()를 살펴보면, 먼저 더미 노드 하나를 만들어준다. 이 더미노드는 생성 당시 위에서 정의된 생성자로 인해 '0'이라는 값을 가진 하나의 노드가 생성된다.
• 이제, 이 노드를 추적할 수 있는 포인터 curr도 설정 해 준다.  여기서의 '추적' 이란 말은, 노드를 추가 해야할 때, 어디에 추가해야할지를 트래킹 하는 포인터이다.
• while list1 and list2 : list1과 list2의 노드들이 존재하는동안 반복한다.
• 만약, list1의 노드값이 list2의 노드값보다 작다면, 현재(curr)의 다음 노드를 list1로 설정해준다. 왜냐하면 현재 curr노드의 값은 0이므로, 0 다음에 제일 작은 수를 0의 다음값으로 설정 해 준다. 그리고, 이미 list1의 현재값은 추가되었으므로, list1.next를 통해 다음 while loop에서는 다음 노드 값을 비교 할 수 있도록 포인터를 업데이트 해 준다. 또한, curr에도 방금 추가된 노드가 있으므로(원래 curr은 더미 노드인 '0'을 가리키고 있었음), curr또한 업데이트 해 준다.
• 만약 list1의 노드값이 list2의 노드값보다 크다면(즉, 이 케이스에서는 list2의 노드값이 다음에 이어져야 한다),  현재 노드의 다음값으로 list2를 해 준다. 그 다음, 위에서 했던것과 같이 list2의 노드 포인터를 다음 노드로 업데이트 해 주고, 현재값을 방금 추가한 list2로 업데이트 해 준다.
• while문에서 두 연결 리스트의 모든 노드들을 비교하고 병합 작업을 마친 후, 마지막 if문을 살펴보자
• 먼저, 두 연결 리스트중 하나라도 노드가 남아있는 연결 리스트가 존재할 경우, 현재노드(여기서의 현재 노드는 합쳐진 연결 리스트의 맨 마지막 일것이다)의 next로 남아있는 리스트를 더해준다. 
• 결국 마지막엔 dummy.next를 리턴하면 처음에 만들었던 더미노드값 '0'뒤의 모든 값들을 리턴 할 것이다. 

 

※ 몰랐거나, 오랜만에 다시 기억난 내용들: 

 

- 나는 첫번째 while문에서 연결리스트의 끝까지 검사하는 조건을 while list1.val != None and list2.val != None으로 생각했다. 사실 이게 더 정확한(?) 코드이지만, 런타임이 더 느려질 것이다. 이유는 다음과 같다. 우리는 노드의 값이 무엇인지는 여기서 알 필요는 없다. 여기선 노드의 끝에 도달했는지 아닌지만 알면 되므로, 굳이 노드의 값이 None인지는 비교해 줄 필요가 없다. 만약, 내가 처음 생각한것 처럼 list1.val != None을 하게되면, 노드의 속성에 한번 더 불필요하게 접근하게 되므로(.val은 노드의 속성에 접근), 런타임이 늘어난다.

 

- 파이썬의 다중할당(Multiple Assignment) : list1, curr = list1.next, list1 부분을 살펴보면, 파이썬에서는 다중 할당을 할 수있다. 사실 문법 자체가 직관적이라 바로 이해할 수 있었지만, 까먹었다가 되찾은 내용이니 여기에 기록하겠다.

 

- if list1 or list2 : 여기서 list1과 list2는 노드를 참조하는 포인터일뿐, 연결 리스트 전체를 의미하는것은 아니다. 여기서는 list1 또는 list2중 하나라도 참이거나 아닐 경우를 판단하는 구문인데, 포인터의 참 / 거짓을 어떻게 확인 할 수 있을까? 파이썬에서는 'None(자바에서의 null)'은 거짓(False)로 평가되며, 여기서는 노드를 가리키고 있으면(즉, 남아있는 노드가 있으면) 참으로 판단된다.

 

- list1: Optional[ListNode]는 Python의 타입 힌트(Type Hinting)로, list1이 ListNode 객체이거나 None일 수 있음을 나타낸다. 이는 list1이 연결 리스트의 첫 번째 노드를 참조하는 포인터일 수 있고, 또는 빈 리스트를 나타내기 위해 None일 수도 있음을 의미한다. 즉, Optional 뒤의 square bracket안에는 None이외의 다른 타입을 명시 해 준다. 예를들어, var = Optional[String]이라면, var이라는 변수는 None타입을 가질수도 있고, String을 가질수도 있다는 의미이다(None, String이외의 타입은 올 수 없다). 정적 타입 검사 도구(mypy 등)를 사용하면 타입 불일치 오류를 사전에 감지할 수 있다. Python 자체는 동적 타이핑 언어이므로 타입 불일치로 인한 직접적인 런타임 오류를 발생시키지 않지만, 잘못된 타입을 처리하려고 할 때 AttributeError와 같은 오류가 발생할 수 있다.
타입 불일치가 발생하면 정적 타입 검사 도구에서 타입 불일치 오류(TypeError)가 보고된다.

 

- curr.next = list1 if list1 else list2 : 파이썬에서의 삼항 연산자이다. 이 삼항 연산식을 풀어쓰면 다음과 같다.

if list1 :

   curr.next = list1

else :

   curr.next = list2