[Day4/15] LeetCode 75

Level 1 : day 4

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

오늘의 주제는 어제와 마찬가지로 Linked List 이다.

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.

876. Middle of the Linked List (문제링크)

주어진 연결리스트 head 의 정 중앙에 위치한 노드부터 tail 까지 반환을 하는 문제이다.

만약 중앙 node 의 갯수가 2개라면 뒤에 것을 선택해야한다.

풀이과정

한 번의 iterative 을 통하여 Linked List 의 길이를 잰 후

두 번 째의 반복문을 i = 0 부터 i가 길이 / 2 에 도달 했을 때 반환을 해주면 된다.

예시

홀수 일때,
1 -> 3 -> 5 -> 7 -> 9
size = 5 --> size / 2 = 2
따라서 5 -> 7 -> 9 가 반환된다.

짝수 일때,
1 -> 3 -> 5 -> 7
size = 4 --> size / 2 = 2
따라서 5 -> 7 이 반환된다.

Java Solution

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode temp = head;
        int size = 1;
        
        while (true) {
            temp = temp.next;
            if (temp == null) break;
            size++;
        }
        
        
        temp = head;
        
        for (int i = 1; i <= size/2; i++) {
            temp = temp.next;
        }
        
        return temp;
    }
}

142. Linked List Cycle II (문제링크)

Linked List 가 주어졌을 때 cycle 의 유무를 판단하고 없으면 null 을 반환, 있으면 싸이클의 시작 node 을 반환하는 문제다.

예시)
3 -> 2 -> 0 -> 4 -> 2 -> 0 -> 4 -> 2 -> ...
node.val 이 2 에서 싸이클이 시작되는 것을 알 수 있다.

1 -> 2 -> 3 -> 4 -> null
싸이클이 없기 때문에 null 을 반환해주면 된다

제한 사항
$-10^5$ <= node.val <= $10^5$
$O(1)$ 공간 복잡도를 이용하여 풀이

풀이과정

Cycle 이 있기 위해서는 Linked List 에 최소 2개 이상의 node 가 필요하다.

따라서, 주어진 head 가 null 이거나, head.next 가 null 일 경우 null 을 반환한다.

공간 복잡도를 생각 안 하고 풀 경우 visited 배열을 만들어 쉽게 구현이 가능하다.

공간 복잡도를 생각 할 경우 배열 대신 지나온 node value 을 -100001 이나 100001 로 변경을 해주면 지나왔는지 안 지나왔는지 알 수 있다. (제한 사항에 node 의 값은 $-100000$ ~ $100000$ 이기 때문에)

Java Solution

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return null;
        
        ListNode tail = head;
        
        while (true) {
            if (tail == null) return null;
            if (tail.val == -100001) break;
            tail.val = -100001;
            tail = tail.next;
        }
        
        return tail;
    }
}

역시 Linked List 은 할만한 것 같다!