14. Merge Two Sorted Lists

리트코드

• 정렬되어 있는 두 연결 리스트를 합쳐라
  
  

1. 재귀 구조로 연결

# 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, 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의 값을 비교해 작은 값이 왼쪽에 오게 하고, next는 그 다음 값이 엮이도록 재귀 호출하는 것이 이 코드의 전부이다.
  (엮이면서 점점 하나로 병합되게 된다.)

• if문에서 괄호를 생략해도 동일하게 진행된다.

  • 가장 우선순위가 높은 것은 비교연산(>)이다.

  • 다음으로 not li이다.

  • or보다 and가 먼저 실행된다.

  • but, 명확하게 괄호로 표현하는 게 좋다.

  

• 변수 스왑

  • 스왑하면서 그 다음 값이 역이도록 계속 재귀호출하면, 연결 리스트가 점점 하나로 병합되면서 엮이게 된다.
    마지막에는 L1이 널(Null)이 되면서, 즉 코드에서는 l1이 None이 되면서 재귀가 끝나고 리턴을 시작한다.
  • 실제로는 이처럼 마지막에 리턴을 시작하면 백트래킹되면서 엮이게 된다.
  • 백트래킹이 종료되면 이제 두 정렬 리스트가 병합되어 하나의 연결 리스트가 된다.

  
  
  

<두 연결 리스트 병합 과정>

참조: 참조1