리트코드 - 21. Merge Two Sorted Lists

리트코드 - 21. Merge Two Sorted Lists

출처 - https://leetcode.com/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

두 개의 정렬된 연결 리스트인 list1과 list2의 헤드 노드가 주어집니다.

두 리스트를 하나의 정렬된 리스트로 병합합니다. 이 리스트는 첫 번째 두 리스트의 노드를 연결하여 만들어져야 합니다.

병합된 연결 리스트의 헤드를 반환합니다.

 

의사코드

dummyHead = new ListNode(0) currentNode = dummyHead 반복문 시작 (list1 != null && list2 != null)     if (list1.val <= list2.val)         currentNode의 next를 list1 로 연결         list1을 next 노드로 이동     else        currentNode의 next를 list2 로 연결         list2을 next 노드로 이동            currentNode를 next로 이동 반복문 종료 if (list1 == null)     currentNode의 next를 list2로 연결 else     currentNode의 enxt를 list1로 연결 dummyHead의 next를 리턴

 

풀이코드

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(0);
        ListNode currentNode = dummyHead;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                currentNode.next = list1;
                list1 = list1.next;
            } else {
                currentNode.next = list2;
                list2 = list2.next;
            }
            currentNode = currentNode.next;
        }
        
        if (list1 == null) {
            currentNode.next = list2;
        } else {
            currentNode.next = list1;
        }
    return dummyHead.next;
    }
}

 

코드설명

링크드리스트를 node를 이용해서 구현하는 문제이다.

node는 val값과 next값을 가지고 있고, next를 통해서 node가 연결이 되어있다.

 

일반적인 Singly Linked List에서처럼 dummyHead인 Node를 하나 만들고, 이를 currentNode로 맞춰준다.

그리고 list1과 list2 노드를 순회하는데, 둘 중에 하나라도 null이 나오면 (=끝에 도달하면) 반복문을 종료한다.

각 노드의 값을 비교해서 작은 값을 currentNode의 다음값으로 연결해주면 되는 간단한 문제이다.

둘중에 하나가 null이 도착했다면 끝에 도달했다는 의미이므로, 도달하지 않은 노드를 연결해주어야 한다.

 

+

dummyHead를 만드는 이유는 실제 LinkedList에서도 이유가 같은데, 초기 시작과 null값에 대응하기 쉽기 때문이다.

만약 바로 list1과 list2를 비교한다면, 둘중에 어떤 값으로 시작 하는지에 대해서도 확인해야해서 코드가 복잡해진다.

그리고 이 때 node가 null이라면 val값에 접근하려고 하면 NullPointerException이 발생한다.

따라서, 처음값을 빈 노드로 하나 만들어서 비교하여 연결해주는 것이 안전한 방법이고, 또 이를 항상 제일 마지막을 가리키는 currentNode로 만들어주면 유지보수에 적합해진다.

 

시간복잡도 - O(m + n) (m은 list1 길이, n도 list2의길이)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

초기 코드

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(0);
        ListNode currentNode = dummyHead;

        while (list1 != null && list2 != null) {
        	int x = list1.val;
            int y = list2.val;
            
            if (x <= y) {
                currentNode.next = list1;
                list1 = list1.next;
            } else {
                currentNode.next = list2;
                list2 = list2.next;
            }
            currentNode = currentNode.next;
        }
        
        if (list1 == null) {
            currentNode.next = list2;
        } else {
            currentNode.next = list1;
        }
    return dummyHead.next;
    }
}

원티드 프리온보딩 인턴십 할 때 선택과제로 주어졌던 문제여서 풀려다가 실패했던 문제다.

코드가 남아있길래 들여다봤더니 조금만 수정하면 되서 이렇게 제출해서 풀었다.

Runtime은 0ms인데, Memory가 18.67%로 최악(?) 이었다.

 

굳이 x와 y를 변수선언 하지 않고, 바로 val값을 불러오니까 약 95%로 확 뛰면서 최고의 코드(?) 가 되었다.

코테에서도 빠르게 Node class를 정의하고 써먹으면 좋을것 같다.

 

정리

어떤 값을 순회할 때 node를 사용하면, 코드는 복잡해지지만 런타임은 어마무시(?)하게 빨라진다.