Linked List | Merge Two Sorted Lists

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

두 Linked List를 Merge하라는 문제이다. 두 리스트 모두 이미 순서대로 (작은숫자부터 큰숫자로) 정렬되어있다. 가장 단순한 방법은, 비교를 해가면서 새로운 리스트에 값을 복사하는 방법이 있을 것 같은데, 메모리를 조금 아끼려면, 주어진 Linked List자체를 변형하는 방법이 있다.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode tempHead = new ListNode(-1);
        ListNode curr = tempHead;
        while(l1 != null && l2 != null) {
            if (l1.val <= l2.val){
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if(l1 != null) curr.next = l1;
        if(l2 != null) curr.next = l2;
        
        return tempHead.next;
    }
}

* Time Complexity: O(N)

* Space Complexity: O(1)

 

temp노드를 만들어서 그 노드에 작은 숫자를 연결해주는 식으로 풀이했다. 이렇게 하면 딱 하나의 노드만 생성하고, 그 이후 노드는, 연결고리만 바꾸어주기때문에 메모리를 적약할 수 있다. LinkedList의 숫자대로 1회만 돌기때문에 N, (이는 두 리스트의 크기를 합친것이다)의 시간이 든다. Worstcase가 총 N번의 시간이 들고, 만약 한 리스트에 작은 숫자들만 모여있고, 길이도 짧으면 훨씬 더 많은 시간을 절약할 수 있다. 그런 케이스에서는 일찍 while loop을 빠져나와서, 남은 노드들의 첫번째 노드를 curr.next로 지정해주면 자동으로 모든 리스트를 연결할 수 있기 때문이다. 마지막으로 처음 생성했던 tempHead의 다음 노드를 리턴해주면, List1 또는 List2 노드에서 작은값을 가진 노드가 새로 merge된 Linked List의 Head가 되어서 리턴된다.

 

이 해법으로 풀었을 때, 가장 빠른 속도, 그리고 거의 최상위로 메모리를 effeciency하게 사용했다.

다른사람의 풀이 중, Recursion을 이용해서 푼사람이 있었는데, 코드가 정말 깔끔했다. 

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val <= l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

* Time Complexity: O(N)

* Space Complexity: O(N)

 

이런식의 해법이었는데, 속도는 비슷했지만, 아무래도 recursion을 사용하다보니 stack의 깊이때문인지 memory를 많이 사용했다. 두 풀이법 모두 좋은 해법같다. 아래 코드가 메모리를 조금더 사용했어도 가독성이 더 좋아보인다.

 

 

자, 151마리의 포켓몬이 리자드 뒤로 한줄, 라이츄 뒤로 한줄로 서있다! 하나의 LinkedList대로 줄세워보자! 이미 모든 포켓몬은 낮은 레벨부터 정렬되어있다. 리자드가 라이츄보다 레벨이 낮네? 그럼 피카츄 뒤엔 라이츄! 리자드보다 이브이가 세네? 그럼 라이츄 뒤엔 이브이! 리자드가 꼬북이보다 약하네? 그럼 이브이 뒤엔 리자드! 

 

 

 

Reference

leetcode.com/problems/merge-two-sorted-lists/

Merge Two Sorted Lists - LeetCode

comicbook.com/gaming/news/pokemon-sword-and-shield-gen-1-pokemon/

Here Are Which Original 151 Pokemon Are in Pokemon Sword and Shield