[LeetCode/Java] 21. Merge Two Sorted Lists

0. 문제

https://leetcode.com/problems/merge-two-sorted-lists/submissions/

1. 문제 설명

• 두 개의 정렬된 LinkedList list1과 list2의 head가 주어진다.
• 하나의 정렬된 LinkedList로 병합하라.

2. 문제 풀이

2.1. 접근법

• 두 LinkedList 중 하나가 null이면 나머지 하나를 반환한다.
• list1과 list2를 조회하면서 더 작은 값을 새로운 LinkedList의 원소값으로 사용한다.

3. 코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        
        ListNode ans = new ListNode();
        ListNode tmp = ans;
        
        while(list1 != null && list2 != null) {
            if(list1.val > list2.val) {
                tmp.next = list2;
                list2 = list2.next;
            }
            else {
                tmp.next = list1;
                list1 = list1.next;
            }
            tmp = tmp.next;
        }
        
        if(list1 == null) {tmp.next = list2;}
        else {tmp.next = list1;}
        
        return ans.next;
    }
}

4. 결과