[파이썬 알고리즘 인터뷰][연결리스트] 두 정렬 리스트의 병합

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

정렬된 두 연결 리스트를 오름차순으로 합치기

 

책에서 구현된 코드

    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

 

기억해야할 기법

• 병합 정렬 (17장에서 나온다고 함)
  
  • 재귀를 이용
  • 두 리스트의 포인터가 가리키는 값 중 더 작은 값을 선택
  • 하나씩 소거한 후 재귀의 결과로 결과 연결 리스트가 만들어짐

 

내가 구현한 코드

None

• 또 low level 느낌으로 만들다가 결과가 이상해서 중도 포기
  • 포인터의 next와 비교
  • 삽입 (before -> nw_node, nw_node -> after)
  • C에서 만든 형식으로 풀이하려함
• 복잡한 과정을 매우 깔끔하게 푸는 방식을 알게된 것 같다
• 직접 활용할 수 있는 기회가 있으면 좋겠다