[알고리즘] #Merge Two Sorted Lists

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

Merge Two Sorted Lists - LeetCode

문제

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1->2->3 , 1->2->4

Output:

1->1->2->-2>->3->4

 

풀이

두 개의 정렬된 리스트를 합치는 문제이다.

처음에는 두 번째 리스트를 순회하면서 첫 번째 리스트의 노드 값과 비교하면서 첫 번째 리스트의 노드가 두 번째 리스트의 노드보다 클 때, 두 번째 리스트의 노드를 첫 번째 리스트의 노드 앞에 넣는 것을 생각했었다. 그러나 다음 노드도 아니고 이전 노드에 추가한다는 건 좀 복잡하다고 생각해서 다른 방법을 고민해봤다.

 

코드

재귀 함수를 이용해서 두 리스트를 순회하는 방법으로 푼 풀이이다.

less와 more 변수를 이용해서, 두 리스트의 노드 값을 비교해서 더 작은 값인 리스트를 less에, 큰 값을 가진 리스트를 more에 저장한다.

아래 그림과 같이 풀이된다.