목차

• 두 정렬 리스트의 병합
  • 문제
• 풀이
• 풀이과정
  • 스왑 Swap
  • 재귀 호출
  • 시각화

👀, 🤷‍♀️ , 📜
이 아이콘들을 누르시면 코드, 개념 부가 설명을 보실 수 있습니다:)

두 정렬 리스트의 병합

난이도| ★
리트코드 819. Merge Two Sorted Lists

문제

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example2:

Input: list1 = [], list2 = []
Output: []

Example3:

Input: list1 = [], list2 = [0]
Output: [0]

[제한]

• The number of nodes in both lists is in the range [0, 50]
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

[전제]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

풀이

들어가기 전 알아 둘 개념

• 병합정렬

풀이과정

여기서는, 정렬된 리스트라는 점이 중요하다.
이 문제는 정렬된 두 리스트를 주는 것 이므로 병합 정렬의 마지막 부분을 이용하면 된다.
죽 첫 번째 값부터 차례대로만 비교하면 한 번에 해결된다(첫 번째부터 비교하면서 리턴하면 쉽게 풀 수 있는 문제다)

먼저 전체 코드부터 살펴보자.

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

코드만 보면 이해가 되지 않으니 하나씩 뜯어보겠다.

1) 스왑 Swap: 먼저 l1 과 l2 의 값을 비교해 작은 값이 왼쪽에 오게 하고,
2) l1.next로 그다음 값이 엮이도록 재귀 호출한다
이것이 이 전체 코드의 전부이다.

스왑 Swap

조금더 세부적인 설명을 위해
여기서 첫 번째 if 문인 괄호로 엮인 부분과 변수를 스왑 Swap 하는 부분부터 살펴보자.

if (not l1) or (l2 and l1.val > l2.val): # 괄호 생략 가능 # (not l1) or (l2 and (l1.val > l2.val))
  l1, l2 = l2, l1 

➕ or 보다 and 가 먼저 실행된다는 점을 알아두자
➕ 또한 l1.val은 l1의 value 즉 l1의 값인 1,2,4를 지칭하는 것이다.

l1 과 l2 의 값을 비교해 작은 값이 왼쪽에 오게 하고,
이제 다음과 같이 변수를 스왑한다.
l1, l2 = l2, l1

또한 조건에 not l1있는 이유는

Example3:

Input: list1 = [], list2 = [0]
Output: [0]

를 처리하기 위해서 이다.

재귀 호출

if l1:
  l1.next = self.mergeTwoLists(l1.next, l2) 

이후에는 l1 의 next 를 재귀호출하면서 다음번 연결 리스트가 계속 스왑될 수 있게 한다.

시각화

이제 전체를 실행하면 연결 리스트가 어떻게 변경되는지, 다음 그림에서 살펴보자.
여기서 중요한 것은 노드 자체를 옮긴다는 점이다.
(노드에 포함되어있는 꼬리 선까지 같이 움직인다는 점에 주의하자)

먼저, 이 그림에서 L1 과 L2 는 두 연결 리스트의 첫 번째 값을 각각 가리킨다.

• 참고로 그림 에서는 구분을 쉽게 하기 위해 대문자 L 을 사용했지만, 코드에서는 소문자 l 을 사용한다.
• 즉 그림에서 L1 과 L2 는 코드에서는 변수 l1 과 l2 가 된다.
• 그런데 아래 그림은 l1.val > l2.val를 만족시키지 못하므로 swap하지 않고 첫번쨰 if 문을 실행시키지 않는다.
  

그럼 아직 l1이 끝나지 않았으므로 두번째 if문이 실행된다.

• 두번째 if문은 l1의 next로 가게 하여 다음 수와 l2를 비교하게 해준다.(재귀함수 호출)
  

그럼 위에서 재귀함수를 호출했으니 바뀐 환경에서 함수를 다시 시작해보자

• l1.val > l2.val이므로 두 값을 swap하는 첫번쨰 if문을 실행시킨다.
• 노드 자체를 swap하는 것이기 떄문에 그 노드가 갖고있는 링크까지 같이 옯겨진다는것에 유의하자
  

위의 과정을 L1이 마지막으로 갈 때 까지 반복하는 것이다

그럼 계속 반복해서 내려가보자
이제 두번 째 if문을 실행한다.

• 즉 L1이 이어진 다음 노드에 위치한다.
  

이제 다시 처음 if문으로 돌아가자.

• l1.val > l2.val이므로 두 값을 swap하는 첫번쨰 if문을 실행시킨다.
  

그럼 위의 방법대로 계속 해보면 아래의 과정을 거쳐 정렬이 완성된다

난 이 풀이를 이해하면서 어떻게 L2가 움직이지 않고도 정렬이 되나 했었는데 이는 L1이 지나가면서 정렬이 된다라고 생각하면 편할 것 같다.
실제로도 L1이 지나간 자리는 모두 정렬이 되어있다.