[Top Interview Questions] 21. Merge Two Sorted Lists

정답)

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 마지막에 병합된 리스트의 헤드를 찾기 위해 저장해 놓은 노드
        header = ListNode(-1)
        
        # 병합할 리스트를 선형하기 위한 노드 
        start = ListNode(None)
        header.next = start
        
        # 두 리스트 모두 검색해야될 노드가 남아있을 때
        while list1 and list2:            
            if list2.val > list1.val:
                start.next = ListNode(list1.val)
                start = start.next
                list1 = list1.next
                
            else:
                start.next = ListNode(list2.val)
                start = start.next
                list2 = list2.next
        
        # list1만 아직 검색해야될 노드가 남아있을 때
        while list1: 
            start.next = ListNode(list1.val)
            start = start.next
            list1 = list1.next
        
        # list2만 아직 검색해야될 노드가 남아있을 때
        while list2: 
            start.next = ListNode(list2.val)
            start = start.next
            list2 = list2.next
        
        # 병합된 리스트의 헤드 노드를 리턴
        return header.next.next

문제)

문제출처

두 개의 정렬된 연결 리스트(Linked List)의 헤드 2개가 주어집니다. 

 

두 개의 정렬된 연결 리스트를 하나의 정렬된 연결 리스트로 병합하시오.

새로 병합된 리스트의 헤드를 리턴하시오.

 

예시 1

예시 1)

list1 = [1, 2, 4], list2 = [1, 3, 4]

output = [1, 1, 2, 3, 4, 4]

 

예시 2)

list1 = [], list2 = []

output = []

 

예시 3)

list1 = [], list2 = [0]

output = [0]

풀이)

기본 원리)

1번째 리스트와 2번째 리스트의 노드의 정수값을 비교합니다. 이 비교과정은 첫 번째 혹은 두 번째 리스트의 모든 노드들이 병합될 리스트에 추가되었을 때까지 이루어집니다.

 

비교과정:

• 1번째 리스트의 노드가 2번째 리스트의 노드보다 값이 작을 경우 1번째 리스트의 노드를 병합 후 1번째 리스트의 다음 노드를 확인합니다.
• 2번째 리스트의 노드가 1번째 리스트의 노드보다 값이 같거나 작을 경우 2번째 리스트의 노드를 병합 후 2번째 리스트의 다음 노드를 확인합니다.

만약 둘 중 하나의 리스트라도 Null에 도착했다면, 다른 리스트에 남아있는 노드들을 체크합니다. 남는 노드들이 있다면 그 순서대로 병합된 리스트의 마지막에 추가해 줍니다. 그리고 아까 지정해 놓은 header.next.next를 리턴해줍니다.

 

header.next.next

header와 start)

header 변수는 최종적으로 병합된 리스트의 헤드 노드를 찾을 때 사용 됩니다. 위 그림을 참조하시면 되겠습니다.

 

start 변수는 병합된 리스트를 선형하는데 사용됩니다. node = node.next라는 방식을 사용해 리스트 내의 가리키고 있는 위치를 계속 업데이트합니다.

 

start = start.next

만약 header 없이 start만 있었다면 나중에 그 리스트의 시작점을 찾을 수 없게 됩니다.

 

header가 필요한 이유

그래서 header는 병합된 리스트의 헤드를 찾기 위해, start는 리스트를 선형 하며 새로운 노드를 추가되는 데 사용된다라고 생각하시면 되겠습니다.

 

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        header = ListNode(-1)
        start = ListNode(None)
        header.next = start

while list1 and list2)

위 문장은

while list1 is not None and list2 is not None와 같은 뜻입니다.

 

즉 list1과 list2가 둘 다 Null이 아닐 때 수행한다는 while 문입니다.

 

주의해야 될 건 list1과 list2는 리스트가 아닌 노드입니다. (함수의 parameter를 참고하세요)

그러므로 list1과 list2가 Null이 아닌 경우에는 이 두 노드들이 정수값을 지닌 노드라는 뜻이겠죠.

 

list1 list2

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        header = ListNode(-1)
        start = ListNode(None)
        header.next = start
        
        while list1 and list2:

list1 노드 vs. list2 노드)

그럼 이 두 노드들을 비교해 줍니다.

list1의 정수값이 list2의 정수값보다 작을 때, start의 다음 노드가 list1의 정수값을 지니도록 해줍니다.

 

start.next = ListNode(list1.val)

start.next = ListNode(list1.val)

스타트 노드의 다음 노드는 list1의 val값을 가진 노드이다.

 

아까 start는 선형 할 때 쓰인댔죠?

새로운 노드를 병합된 리스트의 끝에 저장하기 위해선 start를 옆으로 옮겨야 됩니다.

그래서 start의 위치를 방금 저장한 새로운 노드의 위치로 옮겨줍니다.

start  = start.next

 

이렇게 list1의 값을 저장해 줬으니 list1 또한 다음 노드를 비교하기 위해 위치를 한 칸 오른쪽으로 옮겨줍니다.

list1 = list1.next

 

start = start.next / list1 = list1.next

만약 list2의 정수값이 list1의 정수값보다 같거나 작을 때, 똑같은 원리를 사용해 병합된 리스트의 추가해 줍니다.

 

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        header = ListNode(-1)
        start = ListNode(None)
        header.next = start
        
        while list1 and list2:            
            if list2.val > list1.val:
                start.next = ListNode(list1.val)
                start = start.next
                list1 = list1.next
                
            else:
                start.next = ListNode(list2.val)
                start = start.next
                list2 = list2.next

두 리스트 중 하나라도 검색 완료되면)

list1이나 list2가 Null이 된다는 것은 그 리스트는 전부 검색이 끝났고 병합된 리스트에 추가했다는 뜻이 됩니다.

 

예를 들어 list1의 리스트의 노드들이 전부 추가되었다고 칩시다.

그러면 list2의 리스트들의 노드들은 아직 남아있다는 뜻이 됩니다.

 

list1이 전부 검색된 반면 list2는 아직 3이 남아있습니다.

그러므로 아까와 같이 while list2를 사용해서 list2가 Null이 될 때까지 남는 노드들을 추가해 줍니다. 비교과정을 제외한 추가해 주는 방법은 똑같습니다. 

 

비교를 해주지 않는 이유는 이미 두 리스트 중 가장 작은 부분은 위에서 전부 추가되었습니다. 

지금은 작은 노드들을 제외한 남는 노드들을 추가하는 것이기 때문에 그냥 순서대로 추가해 주시면 됩니다.

 

그렇게 두 리스트들의 노드들이 전부 추가가 된다면 병합된 리스트의 헤드, 즉 header.next.next를 리턴해줍니다.

 

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        header = ListNode(-1)
        start = ListNode(None)
        header.next = start
        
        while list1 and list2:            
            if list2.val > list1.val:
                start.next = ListNode(list1.val)
                start = start.next
                list1 = list1.next
                
            else:
                start.next = ListNode(list2.val)
                start = start.next
                list2 = list2.next
            
        while list1: 
            start.next = ListNode(list1.val)
            start = start.next
            list1 = list1.next
        while list2: 
            start.next = ListNode(list2.val)
            start = start.next
            list2 = list2.next
        
        return header.next.next

예시)

list1 = [1, 3, 3], list2 = [2]

 

(-1) -> (Null)

 

(while list1 and list2)    # list1과 list2 모두 살아있음

(2 > 1)

(-1) -> (Null) -> (1)

 

list1 = [1, 3, 3], list2 = [2]

 

(while list1 and list2)    # list1과 list2 모두 살아있음

(3 > 2)

(-1) -> (Null) -> (1) -> (2)

 

list1 = [1, 3, 3], list2 = [2]

 

(while list1)    # list1만 살아있음

(-1) -> (Null) -> (1) -> (2) -> (3)

 

list1 = [1, 3, 3], list2 = [2]

 

(while list1)    # list1만 살아있음

(-1) -> (Null) -> (1) -> (2) -> (3) -> (3)

 

list1 = [1, 3, 3], list2 = [2]

 

  (-1)       ->     (Null)           ->             (1)               -> (2) -> (3) -> (3)

header                                    리턴해야 되는 헤드   

 

return header.next.next

 

 

머리로는 이해하지만 말로 설명하는 건 정말 어려운거 같습니다! 선생님들이 존경스럽군요 (교수님 제외)

 

그래도 복습도 잘되고 처음에는 우물쭈물했던 게 이제는 머릿속에서 떠오르는 게 신기합니다.

빨리 미디엄도 풀어보고 절망해보고 싶네요 ㅎㅎ

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)