[JAVA] LeetCode 21 - Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new sorted list.

The new list should be made by splicing together the nodes of the first two lists.

 

Example 1:

 

두 개의 정렬된 연결 리스트를 병합하여 하나의 새로운 정렬된 리스트로 반환하라.

새로운 리스트는 주어진 두 개의 연결 리스트 노드를 함께 분할하여 만들어야 한다.

 

 

풀이 방법

1. 루트 노드와 초기에 생성한 루트 노드의 주소를 가지는 head 노드를 만든다.

2. 주어진 연결 리스트(l1,l2)가 모두 null이 될 때까지(마지막 노드까지 탐색), 반복문을 수행한다.

3. val1과 val2에 각각 현재 리스트(l1, l2)의 값을 저장한다. null일 경우, val 범위를 벗어나는 101을 저장한다.

4. 루트 노드에 이어붙일 새로운 노드 객체를 하나 만든다.

5. val1과 val2를 비교하여, 더 작은 값을 새로운 노드 객체의 값으로 할당한다.

5. 현재 리스트(l1, l2)의 주소를 현재 노드와 연결된 다음 노드의 주소로 변경한다.

6. 루트 노드의 next에 새로 생성한 노드를 연결한다.

7. 루트 노드도 5번과 마찬가지로, 현재 노드의 주소를 연결된 다음 노드의 주소로 변경한다.

 

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode root = new ListNode();
        ListNode head = root;
        
        while(!(l1 == null && l2 == null)) {
            int val1 = l1 != null ? l1.val : 101;
            int val2 = l2 != null ? l2.val : 101;
            
            ListNode newNode = new ListNode();
            
            if(val1 >= val2) {
                newNode.val = val2;
                l2 = l2.next;
            } else {
                newNode.val = val1;
                l1 = l1.next;
            }
            
            root.next = newNode;
            root = root.next;
        }
        
        return head.next;
    }
}