[Leetcode Top Interview 150] 21. Merge Two Sorted Lists

난이도 : easy

문제링크

• 두개의 정렬된 링크드리스트가 주어진다
• 두개의 링크드리스트를 하나의 정렬된 링크드리스트로 병합하라

 

1. 접근법

• 정렬되어 있으므로 값을 비교하여 새로운 노드에 순서대로 추가한다

 

2. 의사코드

while (list1, list2가 null이 아닐때까지) {
    if (list1.val가 list2.val 보다 크다면) {
        tmp.next = new ListNode(list1.val);                
        list1 = list1.next;
    } else {
        tmp.next = new ListNode(list2.val);
        list2 = list2.next;
    }

    tmp = tmp.next;            
}

if (list1 != null) {
    tmp.next = list1;
}

if (list2 != null) {
    tmp.next = list2;
}

return ans.next;

 

3. 구현 코드

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode ans = new ListNode();
    ListNode tmp = ans;

    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            tmp.next = new ListNode(list1.val);
            list1 = list1.next;
        } else {
            tmp.next = new ListNode(list2.val);
            list2 = list2.next;
        }

        tmp = tmp.next;
    }

    if (list1 != null) {
        tmp.next = list1;
    }

    if (list2 != null) {
        tmp.next = list2;
    }

    return ans.next;
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 노드를 순회함
• 공간복잡도 : O(n) - 모든 노드를 생성해야 함

 

5. 개선점

• 잘 모르겠다

 

6. 회고

• 다른 분들도 비슷하게 풀었다