[LeetCode] 21. Merge Two Sorted Lists - Java

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

Merge Two Sorted Lists - LeetCode

---

문제

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

---

풀이

풀이 과정

오름차순으로 정렬되어 있는 두 개의 연결 리스트가 주어질 때 두 개의 리스트가 병합된 리스트를 구해야한다.
새로운 리스트를 하나 생성하고 두 개의 리스트를 비교해가며 작은 값 부터 차례대로 붙여나가는 방식으로 풀이한다.

우선 두 리스트 중 어느 한쪽이 null 이라면 merge할 대상이 없는 것이므로 다른쪽의 리스트를 바로 return 한다.

// 두 리스트중 하나의 리스트가 null이라면
// merge할 대상이 없으므로 다른 리스트를 return
if(list1 == null) return list2;
if(list2 == null) return list1;

 

다음으로 최종적으로 반환할 결과 리스트를 하나 생성하고 노드를 이어 붙이기 위해 포인터를 지정한다.

// 반환할 결과 List
ListNode result = new ListNode(0);
ListNode pointer = result;

 

list1과 list2 중 하나의 탐색이 끝날때 까지 반복하며 두 리스트의 노드 중 작은 값을 선언한 포인터의 next값으로 연결해 주고 탐색한 리스트의 노드와 포인터를 한 칸씩 이동한다.

// 두 리스트 중 하나의 끝에 도달할 때까지 반복
while(list1 != null && list2 != null){
    // list1과 list2의 노드 중 작은값을 포인터의 next값으로 연결
    if(list1.val < list2.val){
        pointer.next = list1;
        // list1의 노드 이동
        list1 = list1.next;
    } else {
        pointer.next = list2;
        // list1의 노드 이동
        list2 = list2.next;
    }

    // 포인터 이동
    pointer = pointer.next;
}

 

두 리스트 중 어느 한쪽이 null이 되어 탐색이 종료되면 노드가 남아있는 리스트의 노드들을 결과 리스트에 연결한다.

// 두 리스트 중 값이 남아있는 나머지 노드들을 연결
if(list1 != null) pointer.next = list1;
else if(list2 != null) pointer.next = list2;

 

초기에 결과 리스트를 선언할 때 임의의 초기값을 주어 생성하였으므로 처음 노드를 제외한 다음 노드를 최종적으로 return한다.

// 새로 생성한 리스트의 초기값을 제외한 다음 노드를 return
return result.next;

---

최종 코드

/**
 * 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) {
        // 두 리스트 중 하나의 리스트가 null이라면
        // merge할 대상이 없으므로 다른 리스트를 return
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        // 반환할 결과 List
        ListNode result = new ListNode(0);
        ListNode pointer = result;

        // 두 리스트 중 하나의 끝에 도달할 때까지 반복
        while(list1 != null && list2 != null){
            // list1과 list2의 노드중 작은값을 포인터의 next값으로 연결
            if(list1.val < list2.val){
                pointer.next = list1;
                // list1의 노드 이동
                list1 = list1.next;
            } else {
                pointer.next = list2;
                // list1의 노드 이동
                list2 = list2.next;
            }

            // 포인터 이동
            pointer = pointer.next;
        }

        // 두 리스트 중 값이 남아있는 나머지 노드들을 연결
        if(list1 != null) pointer.next = list1;
        else if(list2 != null) pointer.next = list2;

        // 새로 생성한 리스트의 초기값을 제외한 다음 노드를 return
        return result.next;
    }
}

---