[leetcode 21] Merge Two Sorted Lists

Merge Two Sorted Lists

나의 논리

결과 값으로 반환 할 빈 연결리스트 ret을 선언하고
두 연결리스트 l1, l2를 서로 비교해가며 작은 원소순서대로 ret에 이어 붙이고 , 둘 중 하나가 끝에 다 달았을때, 어느 한 연결리스트의 순회를 마치지 못했다면 그것은 그 연결리스트의 값들이 ret에 있는 모든 원소들의 값보다 큰 것이므로 ret 뒤에 그냥 붙여 준다.

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        if l1 is None and l2 is None:
            return None
        
        if l1 is not None and l2 is  None:
            return l1
        
        if l1 is None and l2 is not None:
            return l2
        
        node = ListNode()
        ret = node
        while l1 is not None and l2 is not None:
            
            if l1.val <= l2.val:                
                node.val = l1.val
                l1 = l1.next

                
            else:
                node.val = l2.val
                l2 = l2.next
            
            if l1 is not None and l2 is not None:
                node.next = ListNode()
                node = node.next

            
        if l1 is not None:
            node.next = l1
            
            
        if l2 is not None:
            node.next = l2
            
        return ret

while 반복문 안에서 node.next에 이어 붙일 연결리스트를 생성할때 한가지 실수를 해서 계속 Wrong Answer이 떳다.

node에 값을 넣고 list를 뒤로 옮기는데, 옮긴 l1 또는 l2가 마지막 노드 즉 None 이라면
ret의 현재 위치를 가르키는 node의 후속노드를 만들어 이어 붙일 필요가 없다. 후속 노드를 붙여봤자 리스트는 None 이므로 반복문 시작과 동시에 종료된다.

책에 있는 논리

책에서는 재귀를 이용하여 풀었는데, 코드가 좀 이해하기 힘들다..
>가 다른 연산자보다 우선순위가 높다고 했는데...
리스트가 None 이 들어올 경우가 있는데 이러면 런타임에러가 나는데 어찌 책에 나온 코드대로 하면 되긴 된다.
연산자 우선순위에 대해 내가 뭔가 잘 못 이해하고 있는거 같긴 한데..

일단 그래서 재귀를 사용한 다른 코드를 살펴봤다.

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        if not l1:
            return l2
        
        if not l2:
            return l1
        
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return  l1
            
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

연결리스트를 다룰때 재귀도 꽤 유용한것 같다.