두 개의 연결 리스트 List_1과 List_2가 주어집니다. 이때 해야 할 작업은 List_2의 노드들을 List_1에 한 칸씩 번갈아 삽입하며 병합하는 것입니다. 만약 병합 후에도 List_2에 자리를 찾지 못한 노드가 남아 있다면, 해당 노드들은 'List_2의 남은 원소'로 출력합니다.
예시로 이해하기
입력 −
List_1: 10 → 2 → 1 → 2 → 5
List_2: 3 → 1 → 4 → 5 → 7 → 2
출력 − 병합된 리스트: 10 → 3 → 2 → 1 → 1 → 4 → 2 → 5 → 5 / List_2의 남은 원소: 7 → 2
설명 − List_2의 원소들을 List_1의 교차 위치에 하나씩 끼워 넣으면 List_1은 10 → 3 → 2 → 1 → 1 → 4 → 2 → 5 → 5가 되고, 모든 자리가 찬 뒤에는 7 → 2가 List_2에 그대로 남습니다.
입력 −
List_1: 11 → 12 → 13
List_2: 14 → 15 → 16 → 17 → 18
출력 − 병합된 리스트: 11 → 14 → 12 → 15 → 13 / List_2의 남은 원소: 16 → 17 → 18
설명 − List_1에는 세 개의 노드뿐이므로 노드 사이사이에 List_2의 원소를 넣을 수 있는 자리가 제한적입니다. 그래서 14와 15까지만 삽입되고, 16 → 17 → 18은 List_2에 남게 됩니다.
알고리즘 접근 방식
- 연결 리스트의 첫 번째 노드를 가리키는 헤드(head) 노드를 만듭니다.
- 값(value)과 다음 노드(next)를 데이터 멤버로 갖는 Node 클래스를 정의합니다. 기본 생성자 Node(int val)에서는 value를 val로, next를 NULL로 초기화합니다.
- add(int updated_value) 메서드로 리스트에 원소를 추가합니다.
- updated_value를 생성자에 전달하여 new_node 객체를 생성합니다.
- new_node.next를 head로 설정한 뒤, head를 new_node로 갱신합니다.
- mergeList(TutorialPoint list) 메서드 안에서 다음을 수행합니다.
- n1_curr를 head로, n2_curr를 list.head로 설정합니다.
- n1_next와 n2_next 참조 변수를 준비합니다.
- n1_curr != null && n2_curr != null인 동안 반복합니다. 반복문 안에서는 먼저 n1_next = n1_curr.next, n2_next = n2_curr.next로 다음 노드를 저장한 후, n2_curr.next = n1_next, n1_curr.next = n2_curr로 포인터를 재연결하고, n1_curr = n1_next, n2_curr = n2_next로 두 포인터를 앞으로 이동시킵니다.
- 반복이 끝나면 list.head를 n2_curr로 설정하여 List_2에 남은 부분의 시작점을 저장합니다.
- main() 메서드 안에서 다음을 수행합니다.
- TutorialPoint 객체인 list_1과 list_2를 각각 new TutorialPoint()로 생성합니다.
- list_1.add(13), list_1.add(12), list_1.add(11)로 List_1에 원소를 추가합니다.
- list_2.add(18), list_2.add(17), list_2.add(16), list_2.add(15), list_2.add(14)로 List_2에 원소를 추가합니다.
- list_1.mergeList(list_2)를 호출하여 List_2의 원소를 List_1에 병합합니다.
- 최종 리스트를 화면에 출력합니다.
구현 예제
public class TutorialPoint{
Node head;
class Node{
int value;
Node next;
Node(int val){
value = val;
next = null;
}
}
void add(int updated_value){
Node new_node = new Node(updated_value);
new_node.next = head;
head = new_node;
}
void mergeList(TutorialPoint list){
Node n1_curr = head, n2_curr = list.head;
Node n1_next, n2_next;
while (n1_curr != null && n2_curr != null){
n1_next = n1_curr.next;
n2_next = n2_curr.next;
n2_curr.next = n1_next;
n1_curr.next = n2_curr;
n1_curr = n1_next;
n2_curr = n2_next;
}
list.head = n2_curr;
}
public static void main(String args[]){
TutorialPoint list_1 = new TutorialPoint();
TutorialPoint list_2 = new TutorialPoint();
list_1.add(13);
list_1.add(12);
list_1.add(11);
list_2.add(18);
list_2.add(17);
list_2.add(16);
list_2.add(15);
list_2.add(14);
list_1.mergeList(list_2);
System.out.println("Merged list is:");
Node temp = list_1.head;
while (temp != null){
System.out.print(temp.value + " ");
temp = temp.next;
}
System.out.println();
}
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Merged list is: 11 14 12 15 13 16
반복문은 노드 삽입을 먼저 수행한 뒤 다음 노드로 이동하기 때문에, List_1의 마지막 노드를 처리하는 시점에 List_2의 노드 하나(16)가 추가로 연결됩니다. 따라서 프로그램 출력에는 16까지 포함되어 있으며, 이때 List_2에는 17 18이 남게 됩니다.
시간 복잡도
이 알고리즘은 두 리스트를 한 번씩만 순회하므로 시간 복잡도는 O(min(m, n))입니다. 또한 기존 노드들의 포인터만 재연결할 뿐 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 여기서 m과 n은 각각 List_1과 List_2의 길이입니다.