leetcode 21. Merge Two Sorted. Lists 리트코드 21. 두 정렬 리스트의 병합 문제 풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

https://leetcode.com/problems/merge-two-sorted-lists/

Merge Two Sorted Lists - LeetCode

 

입력: 리스트 노드 1, 리스트 노드 2

출력: 두 리스트 노드를 병합한 리스트 노드

 

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

유의 사항: 각 리스트 노드가 비어있을 수도 있다. 그러면 빈 리스트 노드를 출력한다.                                                                                                                                                                                                                                                     

생각 과정

l1 = [1,3,4]

l2= [1,2,3]

--> [1,1,2,3,3,4]

 

이렇게 되는 것인데, 그냥 리스트와는 달리 연결리스트이기 때문에 2의 위치가 바뀌게 되면, 그다음 .next 까지 딸려서 이동하게 된다는 것을 고려해야 한다.

두 연결 리스트를 합치는 것을 다 l1으로 이동시키는 것으로 해결할 수 있다.

l2의 원소가 l1보다 크면 l1으로 이동시켜서 l1 하나의 정렬된 리스트로 만드는 것이다.

l2 원소를 l1으로 이동시키는데, 옮길 것이 없을 때까지 반복하므로 재귀로 해결할 수 있다.

풀이

# 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