[Day3/15] LeetCode 75

Level 1 : day 2

오늘은 LeetCode 75 Level 1 을 시작한지 3일차다.

오늘의 주제는 Linked List 이다. 학부시절 때 가장 좋아했던 자료구조였었다. (가장 싫어했던 자료구조는 heap, 증명하기 정말 싫었음...)

https://leetcode.com/study-plan/leetcode-75

This study plan is for those who want to prepare for technical interviews but are uncertain which problems they should focus on. The problems have been carefully curated so that levels 1 and 2 will guide beginner and intermediate users through problems that cover the data structures and algorithms necessary to succeed in interviews with most mid-tier companies. While level 3 provides material to help users whose targets are top-tier companies.

21. Merge Two Sorted Lists (문제링크)

연결리스트 list1 과 list2 가 주어졌을 때 오름차순으로 두 연결리스트를 합쳐서 새로운 연결리스트를 반환하는 문제다.

주어진 list1 과 list2 은 오름차순으로 되어있다.

풀이과정

문제의 제한사항은 다음과 같다,
The number of nodes in both lists is in the range [0, 50].

즉 해당 문제는 반복문으로 list1 과 list2 의 node 들을 비교하며 하나의 연결리스트를 만들어주면 된다.

따라서, 시간복잡도 $O(n + m)$ 으로 충분히 구현 가능하다. $where$ $n = list1.length$, $m = list2.length$

대신 이런 문제는 edge case 을 잘 알아봐야한다.

1. list1 과 list2 가 null 일 경우
2. list1 과 list2 둘 다 null 이 아닐 경우
3. list1 만 null 이 아닐 경우
4. list2 만 null 이 아닐 경우

1번 : list1.val 과 list2.val 이 더 이상 없기 때문에 더 이상 반복문이 유지될 필요가 없다.

2번 : list1.val 과 list2.val 을 비교하여 반환할 리스트에 더 작은 값을 넣어주면 된다.

3번 : list1.val 만 반환할 리스트에 넣어주면 된다.

4번 : list2.val 만 반환할 리스트에 넣어주면 된다.

Java Solution

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode lst = new ListNode();
        ListNode temp = lst;
        while (true) {
        	// case 1
            if (list1 == null && list2 == null) break;
            
            int minVal = 101;
            // case 2
            if (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    minVal = list1.val;
                    list1 = list1.next;
                } else {
                    minVal = list2.val;
                    list2 = list2.next;
                }
            }
            // case 3
            else if (list1 != null) {
                minVal = list1.val;
                list1 = list1.next;
            }
            // case 4
            else {
                minVal = list2.val;
                list2 = list2.next;
            }
            
            temp.next = new ListNode(minVal);
            temp = temp.next;
            
        }
        
        return lst.next;
    }
}

206. Reverse Linked List (문제링크)

LinkedList 의 head 가 주어질 경우 reverse 된 연결리스트를 반환하는 문제이다. 구현은 반복문과 재귀를 통하여 해야한다.

예시)
1 -> 2 -> 3 -> 4 -> NULL
=> 4 -> 3 -> 2 -> 1 -> NULL

풀이과정

이 문제는 굉장히 유명한 문제로, 아마 자료구조 / 알고리즘 수업을 들었다면 한 번씩은 접해봤을듯한 문제다. (4~5년 전에 자료구조 기말고사에서 이 문제를 풀었던것으로 기억한다)

이런 종류의 문제 (연결리스트)은 그림을 그리며 구현하는 것이 가장 바람직하다고 나는 생각한다.

그러나 내 악필을 공개하기는 싫기 때문에 간단하게 말로 적어보려고한다.

공통
head 가 null 이거나 head.next 가 null 일 경우 head 를 반환해준다.

반복문

1. 현재 node 을 저장할 current, 지나온 node 을 저장할 prev, 다음 node 을 저장할 next 을 선언한다.

2. 반복문을 current 가 null 이 될 때까지 돌리며,

3. next 에 current 의 다음 node 을 넣어주고, current.next 을 prev (지나온 node) 로 넣어준다.

4. prev 에는 다시 current 을 넣어주고, current 에는 next 을 넣어주며 반복한다.

재귀
재귀함수를 이용하여 구현하는 경우 google 에 검색해서 그림을 보며 이해하는것이 훨씬 이해하기 수월할 것이다!

Java Solution

class Solution {
    private ListNode iterative(ListNode node) {
        if (node == null) return node;
        if (node.next == null) return node;
        
        ListNode current = node;
        ListNode previous = null;
        ListNode next = null;
        
        while (current != null) {
            next = current.next;
            current.next = previous;
            
            previous = current;
            current = next;
        }
        
        return previous;
    }
    
    private ListNode recursive(ListNode node) {
        if (node == null || node.next == null) return node;
        
        ListNode newNode = recursive(node.next);
        node.next.next = node;
        node.next = null;
        
        return newNode;
    }
    
    public ListNode reverseList(ListNode head) {
        return iterative(head);
    }
}

이렇게 day 3 - Linked List 관련한 문제 2개를 다 풀었다! 아직까지는 무난한것같다.. (알고리즘 공부 열심히 할것..)