leetcode 21(Merge Two Sorted Lists) - Java

문제

두 목록을 하나의 정렬 된 목록으로 병합한다.
목록은 처음 두 목록의 노드를 함께 연결하여 만들어야 한다.
병합된 연결 목록의 헤드를 반환한다.

예시1

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

예시2

Input: list1 = [], list2 = []
Output: []

예시3

Input: list1 = [], list2 = [0]
Output: [0]

제약조건🔎

두 목록의 노드 수는 범위 내에 있습니다.[0, 50]
-100 <= Node.val <= 100
둘 다 내림차순이 아닌 순서로 정렬됩니다.

풀이

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode merge = new ListNode();
        ListNode curr = merge; 

• list1, list2를 합친 결과를 저장할 ListNode merge를 생성한다.
• curr은 merge에 node를 계속 비교하여 추가한다.

• merge는 병합된 연결리스트를 구성하고 마지막에 병합된 연결리스트의 head를 반환한다.
• curr은 merge의 현재 노드를 가리켜서 계속 값을 비교하면서 추가한다.

        if(list1 == null) return list2; 
        if(list2 == null) return list1; 
        if(list1 == null && list2 == null) return null; 
        
        while (list1 != null && list2 != null) {   
            if(list1.val <= list2.val ) {  
                curr.next = list1;          
                list1 = list1.next;         
            } else {
                curr.next = list2; 
                list2 = list2.next; 
            }
            curr = curr.next;   
        }

list가 비어있는 경우를 먼저 처리한다.

• list1이 비어있으면 list2를 반환한다.
• list2가 비어있으면 list1을 반환한다.
• 둘다 비어있으면 null을 반환한다.

병합 과정 (list1, list2둘다 null이 아닌동안 반복)

• list1의 노드 값이 list2보다 작거나 같으면 현재 노드의 값을 list1의 값으로 하고, list1은 다음 노드를 가리킨다.
• list2도 else문으로 같은 작업을 수행한다.
• if, else 중 하나를 통과하면 다음 노드로 이동한다.

        if(list1 == null) curr.next = list2;
        if(list2 == null) curr.next = list1;
    
        return merge.next; 
    }
}

• list1이 null이면 list1이 먼저 종료되어 list2에 노드가 남는다.
  • 다음 노드는 list2의 노드이므로 추가한다.
• list2가 null이면 list2가 먼저 종료되어 list1에 노드가 남는다.
  • 다음 노드는 list1의 노드이므로 추가한다.

merge의 첫 번째 노드(헤드)가 0이므로 next값으로 병합된 노드의 헤드의 next를 반환한다.