LeetCode 21(Merge Two Sorted Lists, java)

0. 문제

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

Merge Two Sorted Lists - LeetCode

 

1. 문제 설명

- 문제에서 2개의 연결 리스트(list1, list2)가 주어진다.

- 두 연결 리스트는 오름차순으로 정렬되어있다.

- 두 연결 리스트를 오름차순으로 병합하는 것이 문제의 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- 우선 문제에서 주어진 연결 리스트(list1, list 2)가 null인 경우를 생각한다.

- 둘 중 하나가 null인 경우에는 나머지 연결 리스트를 반환한다.  

 

b) 두 번째 접근

- 정답을 담을 연결 리스트(result)를 생성한다.

- 문제에서 주어진 연결 리스트 클래스의 속성을 확인해보면 head가 따로 지정되지 않는다.

- 오직 next만을 이용해서 다음 노드를 탐색할 수 있다.

 

- result 연결 리스트는 결과로 반환되어야 하기 때문에 head의 상태를 유지해야 한다.

- 그러므로 result 연결 리스트에 새로운 노드를 삽입해주는 역할의 새로운 연결 리스트(temp)를 생성한다. 

- temp는 result의 첫 번째 노드를 가리키므로, 새로운 노드를 삽입할 때에는 반드시 temp.next를 사용한다.

 

c) 세 번째 접근

- 이제 list 1과 list2를 순차적으로 탐색한다.

- while문을 사용하여 두 리스트가 모두 null이 아닐 때까지 반복하는 조건을 설정한다.

- list1과 list2의 value를 비교하여 더 작은 숫자를 temp 연결 리스트의 새로운 노드로 삽입한다.

 

d) 네 번째 접근 

- 문제에서 주어지는 두 연결 리스트(list1, list2)의 길이를 알 수 없다.

- 그러므로 두 연결 리스트 중 하나의 탐색이 더 빠르게 종료되면 while문은 종료된다.

- 이를 고려하여, list1 또는 list2가 null인 케이스의 처리 작업을 while문 종료 이후에 수행한다. 

 

- 다음 코드를 보며 이해해보자. 

 

3. 정답 코드

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        
        ListNode result = new ListNode();
        ListNode temp = result;
        
        while(list1 != null && list2 != null) {
            if(list1.val > list2.val) {
                temp.next = list2;
                list2 = list2.next;
            }
            else {
                temp.next = list1;
                list1 = list1.next;
            }
            temp = temp.next;
        }
        
        if(list1 == null) {temp.next = list2;}
        else {temp.next = list1;}
        
        return result.next;
    }
}