[알고리즘] Merge Two Sorted Lists

Leetcode의 Merge Two Sorted Lists 문제를 풀어보도록 하겠습니다.

문제

두 개의 정렬된 링크드 리스트를 병합하라. 병합된 링크드 리스트는 두 개의 링크드 리스트를 꼬아놓은 형태로 만들어져야 하고 역시 정렬되어 있어야 한다.

  • 예시
1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

재귀적인 풀이

주어진 링크드가 정렬이 되어 있으므로 head에는 가장 작은 노드가 있고, tail에는 가장 큰 노드가 위치하게 됩니다.
따라서 병합된 링크드 리스트의 head에는 두 개의 head 중에 더 작은 노드가 위치해야 합니다.

예를 들어, 1->2->5, 3->4->5를 병합한다고 생각을 해보면, 병합된 링크드 리스트는 1로 시작해야합니다.
그럼 2->53->4->5가 남습니다. 이 두개의 링크드 리스트의 head를 비교하면 병합된 리스트에 2가 다음으로 와야 합니다.

1
1->2

그 다음에는 53->4->5가 남습니다. 이번에는 3이 더 작으므로 이 값이 병합된 리스트에 다음으로 와야 합니다.

1
1->2->3

그 다음에는 54->5남 습니다. 이번에는 4가 더 작으므로 이 값이 병합된 리스트에 다음으로 옵니다.

1
1->2->3->4

이제는 55가 남는데, 이 두 값은 크기가 동일하므로 어던 값이 다음으로 나와도 무방합니다.

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

위 사고 과정을 관찰해보면, 주어진 링크드 리스트는 점점 짧아지면서 병합된 리스트각 만들어지는 것을 알 수 있습니다.
그리고 매 단계에서 짧아진 입력 리스트를 대상으로 같은 로직을 반복하고 있음을 알 수 있습니다.
따라서, 위 로직은 재귀 알고리즘으로 구현할 수 있습니다.

재귀 알고리즘의 기저 조건은 둘 중에 하나의 링크트의 길이가 0이 되는 것입니다.

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def mergeTwoLists(self, l1, l2):
if not (l1 and l2):
return l1 or l2
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null)
return l1 != null ? l1 : l2;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}

반복적인 풀이

이번에는 재귀적인(recursive) 방법 말고 두 개의 포인터를 이용해서 반복적인(iterative) 방법으로 접근해보겠습니다.

1
2
3
4
1->2->5
^
3->4->5
^

위와 같이 최초에는 두 개의 포인터를 주어진 링크드 리스트이 head를 가리키게 합니다.
그리고 두 개의 값을 비교해서 작은 값을 병합 리스트에 추가하고 작은 값을 가리키던 포인터를 다음으로 전진시킵니다.
이 과정을 두 개의 포인터가 주어진 링크드 리스트의 끝까지 이동할 때 까지 반복합니다.

1
2
3
4
5
1->2->5
^
3->4->5
^
병합 리스트: 1
1
2
3
4
5
1->2->5
^
3->4->5
^
병합 리스트: 1->2
1
2
3
4
5
1->2->5
^
3->4->5
^
병합 리스트: 1->2->3
1
2
3
4
5
1->2->5
^
3->4->5
^
병합 리스트: 1->2->3->4
1
2
3
4
5
1->2->5
^
3->4->5
^
병합 리스트: 1->2->3->4->5
1
2
3
4
5
1->2->5
^
3->4->5
^
병합 리스트: 1->2->3->4->5->5

두 개의 포인터 중 하나가 링크드 리스트에 끝에 다달으면 나머지 포인터는 구지 한 칸씩 진행시킬 필요가 없습니다.
더 이상 비교할 대상이 없으므로 병합 리스트의 맨 뒤에 남은 리스트를 붙여주기만 하면 됩니다.

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def mergeTwoLists(self, l1, l2):
dummy = ListNode(None)
node = dummy
while l1 and l2:
if l1.val < l2.val:
node.next = l1
l1 = l1.next
else:
node.next = l2
l2 = l2.next
node = node.next
node.next = l1 or l2
return dummy.next

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode node = dummy;

while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
node.next = l1;
l1 = l1.next;
} else {
node.next = l2;
l2 = l2.next;
}
node = node.next;
}

node.next = l1 != null ? l1 : l2;
return dummy.next;
}
}

복잡도

MN을 2개의 주어진 링크드 리스트의 길이라고 했을 때 위 두 개의 알고리즘은 O(M+N)의 시간 복잡도를 가지게 됩니다.
재귀적인 방법이든 반복적인 방법이든 두 개의 링크드 리스트를 처음부터 끝까지 한 번만 읽어내려가기 때문입니다.

공간 복잡도의 경우 두 알고리즘이 동일하게 O(M+N)을 가지게 되는데 이유에는 약간의 차이가 있습니다.
반복적인 알고리즘의 경우, 병합 리스트를 저장하기 위한 추가 공간을 사용하기 때문이지만,
재귀적인 알고리즘의 경우, 함수 호출 스택이 주어진 링크드 리스트의 길이에 비례해서 늘어나기 때문입니다.

문제 출처

공유하기