[리트코드] 21. 두 정렬 리스트의 병합 (Python)

Merge Two Sorted Lists - LeetCode

문제

각각 정렬되어 있는 리스트 노드 2개를 합쳐서 1개의 정렬된 리스트 노드 출력하기

 

과정

1. 두개의 정렬된 연결리스트를 입력받는다.
2. 두 연결리스트를 합치기 위해 새로운 dummy 리스트에 모두 이동시킨 후 정렬한다.
3. 옮길 것이 없을 때까지 반복하고 하나의 리스트가 null이 된경우 남은 리스트는 dummy리스트에 그대로 추가한다.
4. dummy리스트 처음 노드의 다음값부터 반환한다.

 

입력

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

출력

[1,1,2,3,4,4]

 

풀이

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:        
        dummy = ListNode()
        node = dummy    
        while list1 and list2:
            if list1.val < list2.val:
                node.next = list1 
                list1 = list1.next
            else:
                node.next = list2
                list2 = list2.next
            node = node.next
        node.next = list1 or list2
            
        return dummy.next

 

한 줄씩 코드 해석해보기

dummy = ListNode()
node = dummy

• dummy 노드를 생성한다.
• node라는 변수에 dummy를 할당한다.
• dummy 노드는 병합할 리스트의 첫번째 노드의 바로 앞 노드가 된다.

while list1 and list2:
    if list1.val < list2.val:
        node.next = list1 
        list1 = list1.next

• 두개의 리스트가 null이 아닌동안 반복한다.
• 만약 리스트1의 값이 리스트2의 값보다 작다면 node.next 는 list1이 된다.
• 그 후 list1의 포인터를 옮겨주어야 하기때문에 list1은 list1.next가 된다.

    else:
        node.next = list2
        list2 = list2.next

• 만약 리스트 2의 값이 리스트 1보다 작다면 node.next는 list2가 된다.
• 그 후 list2의 포인터를 옮겨주어야 하기때문에 list2는 list2.next가 된다.

    node = node.next

• 모든 확인이 끝난 후 병합된 연결 리스트도 한칸씩 이동해야 하기 때문에 node = node.next로 업데이트 해준다.

node.next = list1 or list2

• while루프를 빠져나오게 되면 list1 이나 list2가 하나는 null이다.
• null이 아닌쪽의 남은 노드를 모두 병합된 리스트 맨 뒤에 붙인다.

return dummy.next

• dummy 노드의 그 다음값부터 반환한다.

 

재귀함수를 이용한 풀이

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        if (not list1) or (list2 and list1.val > list2.val):
            list1,list2 = list2,list1
            
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)
       
        return list1

• 두 연결 리스트를 합치는 것을 다 list1으로 이동시키는 것으로 해결할 수 있다.
• list2의 원소가 list1 보다 크면 list1으로 이동시켜서 list1 하나의 정렬된 리스트로 만드는 것이다.
• list2원소를 list1으로 이동시키는데, 옮길 것이 없을 때까지 반복한다. (재귀)