[HackerRank] JAVA - Merge two sorted linked lists

문제

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ᵗʰ element of the list.

Sample Input

1
3
1
2
3
2
3
4

Sample Output

1 2 3 3 4 

---

코드

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

        SinglyLinkedListNode mergedHead;
        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;
        } else {
            current.next = head2;
        }

        return mergedHead;

    }

• LinkedList에서는 SinglyLinkedListNode current = mergedHead; 처럼 current를 생성하면 current에 mergedHead가 복사되는 것이 아닌 참조가 된다.
• 즉, current의 next를 변경하면 current가 참조하고 있는 mergedHead의 노드의 next도 수정된다.

로직
1) 우선 둘 중에 하나라도 null 값이면 다른 List를 반환한다.
2) 각각 첫 노드의 data를 비교하여 가장 첫 HeadNode를 결정한다.
3) HeadNode가 결정되면 해당 Node로 참조 current 노드를 생성한다.
4) 두 List가 null 이 모두 아닐때까지 더 작은 값을 current.next 값으로 업데이트하고 그 다음 값으로 넘어간다.
5) 위 내용 반복 후 남은 List 값을 마지막에 합쳐준다.