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

1. 문제

leetcode 21.Merge two sorted list
두개의 오름차순으로 정렬된 연결리스트 list1, list2가 주어진다. 두 리스트를 오름차순으로 정렬된 하나의 연결리스트로 만들어 리턴하여라. 두 리스트를 이루고 있는 노드들을 이용해야한다.

2. 연결리스트를 하나씩 탐색한 풀이

먼저 두 리스트 맨 앞에 값을 비교하고 작은 값을 sort 포인터로 가리킨다. sort로 가리킨 리스트는  리스트 포인터를 다음 노드로 옮긴다. 둘 중 어떤 한 리스트가 끝나면 반복을 종료한다. 그리고 남은 다른 리스트의 노드들을 sort에 연결시킨다.

3. 재귀함수를 이용한 풀이

책에서는 재귀함수를 이용해서 간결하게 문제를 풀었다. 별도의 포인터나 연결리스트를 만들지 않고 list1에 합친 연결리스트를 만들었다. 만약  list2가 존재하고 list2의 값이 list1보다 작다면 list1, 2의 값을 서로 바꾼다. 그러면 더 작은 값이 list1에 위치하게 된다. 그리고 list1의 next를 이용해 재귀함수를 호출하면서 정렬이 계속 진행될 수 있도록 한다.
만약 모든 정렬이 끝났다면 list1이 None이 되면서 재귀호출을 멈추고 리턴을 시작한다. 이 과정에서 list1.next = self.mergeTwoList가 실행되면서 함수는 list1 뒤에 있는 값 중에 작은 값을 리턴하고, 결국 전체 연결리스트가 하나로 연결된다.