Merge Two Sorted Lists (Linked List)

LeetCode의 Merge Two Sorted Lists 문제다.

Merge Two Sorted Lists - LeetCode

두 개의 정렬된 연결 리스트를 받아 하나의 정렬된 리스트로 합치는 문제다. 두 연결 리스트는 정렬되어 있기 때문에 단순히 두 리스트 요소들을 비교하면서 결과 리스트에 삽입하는 방식으로 구현하면 다음과 같다.

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    	# 두 리스트 중 하나가 비어있다면 남은 리스트를 그대로 반환
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
            
        # 두 리스트 중 시작 노드가 작은 리스트부터 삽입하여 병합 시작        
        if l1.val < l2.val:
            currentNode = ListNode(l1.val, None)
            l1 = l1.next
        else:
            currentNode = ListNode(l2.val, None)
            l2 = l2.next
        
        # 두 리스트를 비교하며 더 작은 쪽의 노드를 삽입        
        result = currentNode
        while l1 and l2:
            if l1.val < l2.val:
                currentNode.next = l1
                l1 = l1.next
            else:
                currentNode.next = l2
                l2 = l2.next

            currentNode = currentNode.next

        # 한쪽 리스트의 노드를 전부 삽입했다면 다른 리스트의 노드를 전부 삽입
        while l1:
            currentNode.next = l1
            currentNode, l1 = l1, l1.next
            
        while l2:
            currentNode.next = l2
            currentNode, l2 = currentNode.next, l2.next

        # 합병된 리스트의 맨 처음 노드를 반환
        return result

예외 처리로 잊지 말아야 할 것은 두 리스트 중 하나가 비어있거나 합치는 도중 한쪽 리스트에 있는 노드들을 전부 삽입했을 때다. 전자는 남은 리스트를 그대로 반환해주면 되고 후자는 남은 리스트를 병합 리스트에 전부 삽입하면 된다. 왜냐면 리스트의 각 노드를 비교하면서 병합 리스트에 삽입하기 때문에 한 리스트를 전부 삽입할 때까지 다른 리스트가 못 들어가고 남아있었다면 지금까지 삽입된 노드들보다 더 큰 노드들만 포함되어 있기 때문이다.

상위 75%의 준수한 성적을 거둘 수 있었다. 참고를 위해 더 좋은 성적의 코드(20ms)를 참조해보니 다음과 같았다.

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            return l1 or l2
      
        d = c = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                c.next = l1
                l1 = l1.next
            else:
                c.next = l2
                l2 = l2.next
            c = c.next
            
        
        if l1 or l2:
            c.next = l1 or l2
        
        return d.next

훨씬 더 간단한 것을 볼 수 있었는데 일단 맨 처음에 두 리스트 중 하나가 비어있는지 확인할 때 return 구문에서 or 연산자를 이용하는 걸 볼 수 있었다. 몰랐던 사실인데 None 타입과 일반 객체를 or 연산자로 비교하면 일반 객체가 반환된다.

>>> l1 = None
>>> l2 = [2]
>>> l1 or l2
[2]
>>> l2 or l1
[2]

C나 Java 언어에서는 '||' 연산자는 무조건 참/거짓 확인이었는데 파이썬에서는 참으로 취급되는 객체 자체를 반환해주는 것 같다. 이 점을 이용하면 좀 더 유연한 코딩이 가능할 것 같다는 생각이 들었다. 그리고 연결 리스트 특성상 노드를 이어 주기만 하면 노드 뒤에 이어져 있는 노드들도 다 따라오기 때문에 굳이 while l1이나 while l2 같은 반복문으로 연결 리스트에 남아있는 모든 노드들을 붙여줄 필요도 없다는 걸 알 수 있었다.

        # 불필요한 while 반복문
        while l1:
            currentNode.next = l1
            currentNode, l1 = l1, l1.next
            
        while l2:
            currentNode.next = l2
            currentNode, l2 = currentNode.next, l2.next

        # 후속 노드에 대한 연결 설정만으로 충분하다.
        if l1:
            currentNode.next = l1
        elif l2:
            currentNode.next = l2
            
        # 위에서 본 or 연산자를 활용하면 더 간략하게 가능하다.
        if l1 or l2:
            c.next = l1 or l2

아마 예전에 배열로 비슷한 문제를 풀었던 기억이 있어서 위처럼 구현했던 것 같다. 로직 자체는 비슷하지만 구현 과정에서 불필요한 점을 줄이니 속도가 더 향상되는 것을 볼 수 있었다.

 

도서에서는 다음과 같은 재귀 호출 방식으로 푸는 풀이를 제공하고 있다.

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> 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, l2 연결 리스트를 l1 연결 리스트에 병합하면서 정렬하는 방식으로 첫 번째 줄의 조건, 즉 l1이 비어있거나 l1 노드가 l2 노드보다 큰 값을 가리킬 때 이 둘을 교환하면서 항상 l1 노드가 가리키는 연결 리스트에는 작은 값부터 채워지도록 진행하는 것이다. 그리고 l1 노드의 다음 노드를 재귀 호출한 결괏값으로 설정하기 때문에 맨 마지막 노드까지 병합한 후에 자동으로 연결 리스트가 이어진다.

 

중간중간에 l1, l2가 교환되기 때문에 리스트가 대체 어떻게 이어지는지 이해하기가 어렵기 때문에 실제로 써먹을 만한 풀이는 아닌 것 같다.