[Linked List] Merge two sorted linked lists

난이도: ★★☆☆☆ • solved on: 2025-11-07

---

문제 요약

• 문제 유형: 연결 리스트(Linked List), 정렬(Merge)
• 요구사항: 정렬된 두 연결 리스트를 오름차순으로 병합하여 새로운 정렬 리스트를 반환하라.

---

사용 개념

1. 자료구조
   • SinglyLinkedListNode: 단일 연결 리스트 노드 구조
2. 알고리즘/기법
   • 병합 정렬의 병합 단계(Merge step)
   • 투 포인터(Two-pointer)
3. 핵심 키워드
   • 정렬 유지, 연결 리스트 병합, 순차 비교

---

풀이 아이디어 및 코드

🔹 방법 1 : ArrayList 활용 (단순 구현)

1. 문제 분해

   • 두 리스트를 순회하며 모든 노드의 데이터를 ArrayList에 저장.
   • ArrayList를 Collections.sort()로 정렬한 뒤, 새 리스트를 생성.

2. 핵심 로직 흐름

   head1, head2 순차 탐색 → arr에 추가
   Collections.sort(arr)
   arr 순회하며 새로운 연결 리스트 생성
   ``
   

3. 예외 처리

   • 두 리스트 중 하나가 null일 경우 → 다른 리스트를 그대로 반환하면 됨.

코드

static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    SinglyLinkedListNode head1Current = head1;                
    SinglyLinkedListNode head2Current = head2;
    ArrayList<Integer> arr = new ArrayList<>(); 

    while(head1Current != null){
        arr.add(head1Current.data);
        head1Current = head1Current.next; 
    }
    while(head2Current != null){
        arr.add(head2Current.data);
        head2Current = head2Current.next; 
    }

    Collections.sort(arr);

    SinglyLinkedListNode result = new SinglyLinkedListNode(arr.get(0));
    SinglyLinkedListNode resultCurrent = result;

    for(int i = 1; i < arr.size(); i++){
        resultCurrent.next = new SinglyLinkedListNode(arr.get(i));
        resultCurrent = resultCurrent.next;
    }
    return result;
}

---

🔹 방법 2 : 투 포인터 병합 (효율적 개선)

1. 문제 분해

• 이미 정렬된 두 리스트이므로 정렬 과정이 필요 없음.
• 두 리스트의 현재 노드를 비교하며 더 작은 값을 결과 리스트에 추가.

2. 핵심 로직 흐름

   while (head1 != null && head2 != null):
       if (head1.data < head2.data):
           attach head1 → move head1
       else:
           attach head2 → move head2
   남은 노드 전체를 결과 리스트 뒤에 연결

3. 예외 처리

• 어느 한 쪽이 null이면 → 나머지 리스트를 결과의 꼬리에 그대로 연결.

static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    if (head1 == null) return head2;
    if (head2 == null) return head1;

    SinglyLinkedListNode mergedHead;

    // 초기 head 설정
    if (head1.data < head2.data) {
        mergedHead = head1;
        head1 = head1.next;
    } else {
        mergedHead = head2;
        head2 = head2.next;
    }

    SinglyLinkedListNode current = mergedHead;

    // 병합
    while (head1 != null && head2 != null) {
        if (head1.data < head2.data) {
            current.next = head1;
            head1 = head1.next;
        } else {
            current.next = head2;
            head2 = head2.next;
        }
        current = current.next;
    }

    // 남은 노드 연결
    if (head1 != null) current.next = head1;
    if (head2 != null) current.next = head2;

    return mergedHead;
}

---

시간·공간 복잡도

방법 1 (ArrayList)

• 시간 복잡도: O((N+M) log(N+M))
• 공간 복잡도: O(N+M)

방법 2 (투 포인터)

• 시간 복잡도: O(N+M)
• 공간 복잡도: O(1) (새 노드 생성 없이 기존 노드 연결만 변경)

---

어려웠던 점

• 처음에는 단순히 데이터를 모아 정렬하는 방식으로 접근했지만, 공간 낭비가 커 효율이 떨어졌다. 아직 LinkedList에 대한 활용 능력이 부족한 것 같다.

---

배운 점 및 팁

• 정렬된 연결 리스트 병합은 "Merge Sort의 병합 단계" 그대로 구현 가능.
• ArrayList는 직관적이지만, 리스트 병합 시엔 투 포인터 방식이 훨씬 빠르고 메모리 효율적이다.
• null 체크 순서를 잘못 두면 런타임 에러가 발생하므로 항상 루프 진입 전 방어 조건을 먼저 써야 한다.

---

참고 및 링크

• 문제 링크: https://www.hackerrank.com/challenges/merge-two-sorted-linked-lists/problem
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 21. Merge Two Sorted Lists (LeetCode)

• 확장 문제 (GPT 추천):

  • K개의 정렬된 연결 리스트 병합 (Merge K Sorted Lists)
  • Linked List Cycle Detection 문제