[LeetCode] 21. Merge Two Sorted Lists - Java

Merge Two Sorted Lists - LeetCode

 

문제

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

Merge the two lists into 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.

 

두 개의 정렬된 LinkedList를 병합하여 하나의 정렬된 LinkedList를 생성하는 문제이다.

 

---

 

풀이

 

연결리스트 진짜 모르겠다.

알겠는데 문제 보면 다시 모르겠는 기분…

그림을 하나씩 그려가면서 연결리스트 처음에 값을 삽입할 경우, 중간에 값을 삽입할 경우, 끝에 값을 삽입할 경우

각각 어떤 흐름으로 진행되는지 먼저 공부한 후 다른분의 코드에서 약간 힌트를 얻어 풀이했다.

 

/**
 * 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) {
        ListNode dHead = new ListNode(Integer.MIN_VALUE);
        ListNode curr = dHead;

        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;
        }
        if(list1==null){ curr.next = list2;}
        if(list2==null){ curr.next = list1;}

        return dHead.next;
    }
}

 

임시 노드를 생성하고 초기값으로 Integer.MIN_VALUE 를 저장하여 빈 연결리스트를 가리킨다.

현재 노드의 포인터 변수인 curr 은 초기값으로 임시 노드를 가리킨다.

루프로 list1과 list2의 노드들을 순회하면서 두 노드 중 값이 작은 노드를 선택하여 결과 리스트에 추가한 후 다음 노드로 이동한다.

둘 중 하나라도 끝에 도달하면 나머지 남은 노드들을 결과 리스트의 뒤에 모두 추가한다.

최종적으로 dHead.next를 반환하여 실제 정렬된 연결 리스트의 시작 노드를 반환한다.

 

위와 같은 흐름으로 해결할 수 있었다.

 

• 시간복잡도 : O(n) - 두 연결리스트의 노드들을 한 번씩만 방문한다.
• 공간복잡도 : O(1)

 

한문제씩 풀수록 LinkedList가 어떤식으로 동작하는지 감이 좀 오는 것 같다.

 

---

 

다른 사람의 풀이

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if(list1==null){return list2;}
    if(list2==null){return list1;}

    if(list1.val < list2.val){
        list1.next = mergeTwoLists(list1.next,list2);
        return list1;
    }else{
        list2.next = mergeTwoLists(list2.next,list1);
        return list2;
    }
}

재귀를 사용해 풀이하는 방법도 있다.

두 리스트를 반복적으로 순회하지 않고 재귀적으로 병합하면서 효율적인 알고리즘으로 풀이할 수 있다.

하지만 재귀 호출에 따라 함수 호출 스택이 증가하기 때문에 메모리를 많이 사용할 수 있다는 단점이 있을 수 있다.

어떤 알고리즘이 현재 문제에 가장 효율적인지 항상 생각하면서 문제를 풀어야겠다.