cleanUrl: /posts/merge-two-sorted-lists-leetcode-21-performance

요즘 leetcode like top 100을 풀고 있는데 속도를 반드시 개선하고 싶은 문제를 발견했다.

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4

맨 처음 생각한 풀이는

1. ListNode 를 순회 하면서 값을 List 에 add 하고
2. sorting 을 실행 한 뒤에
3. 그 값을을 다시 순회하면서 ListNode 를 만들어 반환하면 되겠다

라고 생각했다.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        
        List<Integer> nums = new ArrayList<>();
        while (Objects.nonNull(l1)) {
            nums.add(l1.val);
            l1 = l1.next;
        } 
        while (Objects.nonNull(l2)) {
            nums.add(l2.val);
            l2 = l2.next;
        }
        Collections.sort(nums);
        ListNode result = new ListNode(nums.get(0));
        ListNode node = result;
        for (int i = 1; i < nums.size(); i++) {
            node.next = new ListNode(nums.get(i));
            node = node.next;
        }
        return result;
    }
}

이건 좀 자존심 상하는데.. 내가 하위 20%라니…

아 물론.. List 를 만들어서 value 를 저장하고 sorting 을 하고 이게 효율적인 알고리즘은 아닐 것이다. ㅠㅠ

분명히 누군가는 while 한번만 쓰고 끝냈을텐데

그래서 다음과 같은 기준을 정했다.

1. while 은 딱 한번만 돌자