[HackerRank] Merge two sorted linked lists

Problem

---

This challenge is part of a tutorial track by MyCodeSchool

Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list. Either head pointer may be null meaning that the corresponding list is empty.

 

Example
HeadA refers to 1 → 3 → 7 → NULL
headB refers to 1 → 2 → NULL

The new list is 1 → 1 → 2 → 3 → 7 → NULL

 

Function Description

Complete the mergeLists function in the editor below.

mergeLists has the following parameters:

• SinglyLinkedListNode pointer headA: a reference to the head of a list
• SinglyLinkedListNode pointer headB: a reference to the head of a list

Returns

• SinglyLinkedListNode pointer: a reference to the head of the merged list

Input Format

The first line contains an integer t, the number of test cases.

The format for each test case is as follows:

The first line contains an integer n, the length of the first linked list.
The next n lines contain an integer each, the elements of the linked list.
The next line contains an integer m, the length of the second linked list.
The next m lines contain an integer each, the elements of the second linked list.

Constraints

• 1 ≤ t ≤ 10
• 1 ≤ n, m ≤ 1000
• 1 ≤  list[i] ≤  1000, where list[i] is the i^th element of the list.

Sample Input

1
3
1
2
3
2
3
4

Sample Output

1 2 3 3 4

Explanation

The first linked list is: 1 → 3 → 7 → NULL

The second linked list is: 3 → 4 → NULL

Hence, the merged linked list is: 1 → 2 → 3 → 3 → 4 → NULL

---

두 개의 정렬된 단일 연결 리스트의 헤드 포인터가 주어졌을 때, 이 두 리스트를 병합하여 하나의 정렬된 연결 리스트로 만들어야 합니다. 주어진 헤드 포인터 중 하나는 null일 수 있으며, 이는 해당 리스트가 비어 있음을 의미합니다.

 

예시

• headA가 가리키는 리스트: 1 → 3 → 7 → NULL
• headB가 가리키는 리스트: 1 → 2 → NULL

병합된 새로운 리스트: 1 → 1 → 2 → 3 → 7 → NULL

 

함수 설명

mergeLists 함수를 완성하세요. 함수는 다음 매개변수를 받습니다.

• SinglyLinkedListNode 포인터 headA: 첫 번째 리스트의 헤드 참조
• SinglyLinkedListNode 포인터 headB: 두 번째 리스트의 헤드 참조

반환값: 병합된 리스트의 헤드 포인터를 반환합니다.

 

입력 형식

• 첫 번째 줄에 테스트 케이스의 수 ttt가 주어집니다.
• 각 테스트 케이스의 형식은 다음과 같습니다:
  • 첫 번째 줄에 첫 번째 연결 리스트의 길이 nnn이 주어집니다.
  • 다음 nnn개의 줄에 첫 번째 리스트의 요소가 주어집니다.
  • 그 다음 줄에 두 번째 연결 리스트의 길이 mmm이 주어집니다.
  • 다음 mmm개의 줄에 두 번째 리스트의 요소가 주어집니다.

첫 번째 리스트: 1 → 3 → 7 → NULL
두 번째 리스트: 3 → 4 → NULL
병합된 리스트: 1 → 2 → 3 → 3 → 4 → NULL

728x90

 

 

Solution

---

// Complete the mergeLists function below.

/*
 * For your reference:
 *
 * SinglyLinkedListNode {
 *     int data;
 *     SinglyLinkedListNode next;
 * }
 *
 */
static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    // 새 리스트의 더미 헤드 노드 생성
    SinglyLinkedListNode dummy = new SinglyLinkedListNode(0);
    SinglyLinkedListNode current = dummy;

    // 두 리스트 모두 null이 아닐 때까지 반복
    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;
    } else {
        current.next = head2;
    }

    // 더미 헤드의 다음 노드를 반환
    return dummy.next;
}

 

1. dummy 노드를 생성하여 병합된 리스트의 시작 부분을 관리합니다.
2. head1과 head2를 비교하여 작은 값을 current.next에 추가하고, 해당 리스트의 다음 노드로 이동합니다.
3. 두 리스트 중 하나가 null이 되면, 나머지 리스트를 통째로 current.next에 연결합니다.
4. dummy.next를 반환하여 병합된 리스트의 시작 노드를 반환합니다.

이 코드는 시간 복잡도 O(n+m)O(n + m)O(n+m)으로, 두 리스트의 길이에 비례하여 작동합니다.

 

* SinglyLinkedListNode 클래스

SinglyLinkedListNode는 단일 연결 리스트 (Singly Linked List)의 각 노드를 나타내는 클래스입니다. 이 클래스는 다음 두 가지 속성을 가지고 있습니다:

1. data: int 타입의 값으로, 노드가 저장하는 실제 데이터입니다.
2. next: SinglyLinkedListNode 타입의 포인터로, 다음 노드를 가리킵니다. 이 속성을 통해 각 노드가 다른 노드와 연결되며, 단일 연결 리스트가 됩니다.

---

코드 분석

 

이 코드는 두 개의 정렬된 단일 연결 리스트를 병합하여 새로운 정렬된 리스트를 생성

1. 더미 노드 생성

SinglyLinkedListNode dummy = new SinglyLinkedListNode(0); 
SinglyLinkedListNode current = dummy;

• dummy는 새로운 리스트의 시작 부분을 나타내는 임시 노드. dummy 노드를 통해 병합된 리스트를 만들고, 최종적으로 dummy.next를 반환하여 리스트의 시작 위치를 알 수 있다.
• current는 현재 위치를 가리키며, dummy 노드에서 시작하여 병합된 리스트를 만들어가면서 순차적으로 다음 노드를 연결한다.

2. 병합 작업 반복문

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; 
}

• 이 while 루프는 두 리스트의 끝에 도달할 때까지 반복
• 각 반복에서 head1과 head2가 가리키는 값(data)을 비교
• head1.data가 head2.data보다 작거나 같으면 current.next를 head1에 연결하고, head1을 다음 노드로 이동
• 그렇지 않으면 current.next를 head2에 연결하고, head2를 다음 노드로 이동
• 마지막에 current = current.next를 통해 current 포인터를 방금 추가한 노드로 이동하여 다음 노드를 연결할 준비를 한다.

3. 남은 노드 연결

if (head1 != null) { 
    current.next = head1; 
} else { 
    current.next = head2; 
}

• while 루프가 종료되면 두 리스트 중 하나는 끝까지 순회된 상태
• 나머지 리스트에 아직 노드가 남아있다면, current.next를 그 남은 리스트의 시작 부분에 연결
• 이를 통해 남아있는 노드들을 병합된 리스트의 끝에 추가할 수 있다.

4. 병합된 리스트 반환

return dummy.next;

• dummy.next는 병합된 리스트의 실제 시작 노드를 가리킨다. dummy 노드는 임시로 사용한 것이므로 반환하지 않고, dummy.next를 반환하여 최종 병합된 리스트의 시작을 제공
   

current.next를 사용한 노드 추가 설명

 

current.next = head1 또는 current.next = head2를 통해 새로운 노드를 추가한다. 이 코드가 동작하는 이유는 current가 현재 병합된 리스트의 끝에 있기 때문이다. 각 반복에서 current.next가 새로운 노드를 가리키게 만들어 리스트가 확장되며, current를 새로 추가된 노드로 이동시키면서 다음 노드를 추가할 준비를 한다.

요약하자면, current.next에 새로운 노드를 설정함으로써 리스트가 확장되며, current를 업데이트하면서 다음 노드를 연결할 수 있다.