[LeetCode#21] Merge Two Sorted Lists

❒ Description

---

제목	Merge Two Sorted Lists
링크	https://leetcode.com/problems/merge-two-sorted-lists/description/
자료구조	선형 자료구조
푼 날짜	7/24

 

 

 

 

 

❒ Solution

---

1. Brute Force 

public static void main(String[] args) {

    // create Test Case
    ListNode node1_3 = new ListNode(4, null);
    ListNode node1_2 = new ListNode(2, node1_3);
    ListNode node1_1 = new ListNode(1, node1_2);

    ListNode node2_3 = new ListNode(4, null);
    ListNode node2_2 = new ListNode(3, node2_3);
    ListNode node2_1 = new ListNode(1, node2_2);

    // O(nlogn)
    List<ListNode> nodeList = new ArrayList<>();
    List<ListNode> mergedNodeList = addNodeRecursively(
            node2_1,
            addNodeRecursively(node1_1, nodeList)
    );
    mergedNodeList.sort(Comparator.comparing(nodes -> nodes.val));
    for (int i = 0; i < mergedNodeList.size() -1 ; i++) {
        mergedNodeList.get(i).next = mergedNodeList.get(i+1);
    }
    mergedNodeList.getLast().next = null;
    System.out.println(mergedNodeList.getFirst());
}

public static List<ListNode> addNodeRecursively(ListNode node, List<ListNode> nodeList) {
    ListNode defaultNode = node;
    if (defaultNode.next != null) {
        defaultNode = defaultNode.next;
        addNodeRecursively(defaultNode, nodeList);
    }
    nodeList.add(node);
    return nodeList;
}

 

내가 최초로 작성했던 코드이다.

• 재귀 구조를 사용하여, 각 노드에 연결된 노드들을 리스트에 추가 
• 리스트 정렬
• 정렬된 리스트를 다시 연결 리스트로 변환

결과적으로 O((n+m)log(n+m))의 시간복잡도를 갖는다.

 

---

 

2. 재귀구조

public static 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(list1, list2.next);
        return list2;
    }
}

 

이 방식은 두 개의 정렬된 리스트를 한 번의 순회로 병합하는 방식이다. 

결과적으로 O(n+m)의 시간복잡도를 갖는다.