[LeetCode] 21. Merge Two Sorted Lists (Python)

- Linked List

 

나의 코드

# 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]:
        # empty list
        cNode = result = ListNode()

        while list1 and list2:
            if list1.val < list2.val:
                cNode.next = list1
                list1, cNode = list1.next, list1
            else :
                cNode.next = list2
                list2, cNode = list2.next, list2
            
        if list1 or list2:
            cNode.next = list1 if list1 else list2

        return result.next

 

코드리뷰

두 개의 정렬된 연결 리스트를 합쳐서 또 다른 하나의 정렬된 연결 리스트를 생성하는 함수를 구현하는 문제이다.

 

1) 연결리스트 구현

먼저 해당 문제에서 연결리스트는 ListNode() 클래스로 노드를 구현하였고

각 노드는 값을 의미하는 val 과 다음 노드를 의미하는 next를 담고있다.

 

2) 두 리스트 병합

 

① 두 리스트의 병합을 담을 하나의 결과리스트 생성(헤드 생성)

cNode = result = ListNode()

결과리스트 result에 ListNode()를 호출하여 초기화하고(첫 노드),

결과 리스트 내의 현재 노드를 의미하는 cNode에 이를 할당하여 서로 같은 주소를 참조하도록 하였다.

 

② 두 리스트 병합을 위한 반복비교 과정

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

list1과 list2가 모두 None이 아닌 경우 반복을 계속 진행한다.

매 반복 세션마다 두 리스트의 현재 노드 값 크기를 비교한다.

더 작은 것을 cNode에 담고, 해당 노드의 다음으로 넘어간다.

 

③ 남는 리스트 처리

두 리스트 중 하나가 모두 결과 리스트에 담긴 경우 나머지 부분을 처리해야한다.

if list1 or list2:
    cNode.next = list1 if list1 else list2

삼항 연산자를 통해 None이 아닌 것을 cNode의 다음 노드로 할당한다.

 

④ 결과 반환

현재 처음에 선언한 result에는 결과리스트의 헤드노드가 담겨있다.

이를 반환하고 함수를 종료한다.