[LeetCode] 21. Merge Two Sorted Lists (Java)

문제

 

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

Merge Two Sorted Lists - LeetCode

 

풀이

 

난이도: Easy

 

정렬되어 주어지는 2가지 NodeList를 정렬된 순서로 병합하는 문제.

 

반복문 풀이와 재귀 풀이 두 가지를 모두 확인해보자.

 

 

반복문 풀이

 

반복문은 두 연결 노드의 값을 비교하여 더 작은 값을 새로운 병합 연결 노드와 연결해주자.

최종적으로는 한쪽의 연결 노드는 모두 병합되고 나머지 한쪽의 연결 노드들만 남게 된다.

 

이때는 나머지 노드들이 이미 서로 정렬되어 연결된 상태이기 때문에 가장 앞의 노드만 연결해주면 된다.

 

 코드

 

 재귀함수 풀이

 

ListNode mergeTwoLists(ListNode list1, ListNode list2) 함수는 list1과 list2가 병합된 연결 노드의 헤더를 반환한다.

 

만약 list1의 첫 노드가 list2 보다 작다면 list1.next는 mergeTwoLists(list1.next, list2) 가 반환하는 병합 연결 노드가 될 것이다.

반대로 list2의 첫 노드가 list1보다 작거나 같은면 list2.next에는 mergeTwoLists(list1, list2.next) 가 연결된다.

 

이처럼 재귀 함수로 구현하면 call stack이 빠르게 쌓여 비효율적이지만 노드 수의 제한이 작기 때문에 충분히 빠르게 해결된다.

 

릿코드에서는 백준과 달리 input값의 범위가 작아서 여러 풀이를 생각해 볼 수 있다는 점은 좋은 것 같다.

 

재귀 함수 코드, 풀이 출처: https://leetcode.com/problems/merge-two-sorted-lists/discuss/9715/Java-1-ms-4-lines-codes-using-recursion