[LeetCode] 21. Merge Two Sorted Lists - 문제풀이

Description

주어진 두개의 오름차순으로 정렬된 LinkedList를 머지하는 문제입니다. 재귀호출과 반복 두가지 방법으로 해결이 가능합니다. 

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.

Solution 1. 반복(Iteration)

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    //1. Iteration
    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;
}

반복(Iteration)을 이용한 방법입니다. 더미 노드(dHead)를 만들어 시작포인터를 저장해 두고 curr 포인터를 만들어 list1,list2 포인터를 움직여서 비교해가며 붙여나갑니다. 반복문이 끝나고 남은 노드들은 이미 정렬된 상태기때문에 그냥 뒤에 붙여주면 됩니다.

Solution 2. 재귀호출(Recusion)

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    //2. Recusion
    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;
    }
}

재귀호출(Recusion)을 이용한 방법입니다. 작은 노드의 next 찾기 위한 다시 next와 재귀호출을 통해 찾아가는 방벙브로 소스는 심플하나 결국 메서드가 스택 메모리 영역에 올라가기 때문에 STO가 발생할수 있다는 점을 기억하셔야 합니다.

Reference

Merge Two Sorted Lists - LeetCode