매일 조금씩

두개의 포인터를 사용하는 것이 포인트다.초반엔 스택을 사용해서 푸는 방법을 생각했는데 그러다 보니 어차피 사라질 노드를 타겟으로 잡게되어서 고려해야할 상황들이 너무많았다.두개의 포인터를 다음과 같은 용도로 사용한다. 첫번째 포인터: 삭제될 노드와 N만큼 차이나는 뒤쪽 노드두번째 포인터: 삭제될 노드를 next로 가지는 노드따라서 두 포인터는 N+1 만큼의 차이를 갖는다.반복문을 통해, 첫번째 노드부터 끝까지 탐색하는데첫번째 포인터가 마지막 노드를 넘어서 null이 될 때, 두번째 포인터는 삭제될 노드를 next로 가리키고 있고,반복문은 멈춘다. 그리고 두번째 포인터의 next 를 next.next로 바꾸면 된다. /** * Definition for singly-linked list. * public c..

합쳐야할 LinkedList가 두개가 아니다.여러개의 LinkedList를 전부 돌면서 하나하나 비교를 하는것은 매우 비효율적이고 방식도 복잡할 것이다.따라서, 전체 노드를 각각으로 보고 정렬시킨후 연결 시키는 방식으로 풀어내야한다.정렬을 위해선 PriorityQueue를 사용하는 것이 가장 효율적이다.Step1) 가장 먼저 value를 보고 정렬해주는 PriorityQueue를 생성해서,주어진 각 리스트의 헤드를 삽입한다. PriorityQueue에 한번 삽입할때의 시간복잡도는 O(log K)이다. (삽입할때마다 정렬하기때문)이걸 삽입하는 수만큼 반복하니 시간복잡도는 O(K log K) K: 리스트 수 이다.Step2)그리고 PriorityQueue를 poll() 하면서 연결하고, poll()된 노드의..

LinkedList 의 개념을 다시 잡을 수 있었다.연결된 노드 객체들은 다음 노드를 가리키는 포인터를 갖는다.사이클이 없다면, LinkedList의 헤드를 가리키는 더미 노드를 임의로 생성해서 활용해도 된다.이 문제에선 그 더미노드를 사용하는 것이 핵심이다. /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */cl..

LinkedList 내에 사이클이 존재하는지 확인하는 문제다. 사이클이 있는지 확인하는 좋은 알고리즘을 발견했다. 빠른 포인터와 느린 포인터 두 개를 사용하여 LinkedList를 탐색하는 방법이다.빠른 포인터는 느린 포인터보다 두 배 빠르게 이동한다.주기가 있는 경우 빠른 포인터는 결국 느린 포인터를 따라잡는다.주기가 없으면 빠른 포인터가 목록의 끝에 도달하고 함수는 False를 반환한다.이 알고리즘은 단일 LinkedList에서 주기를 감지하는 효율적인 방법이다.  /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val..

링크드리스트의 개념을 이해하도록 도와주는 문제였다. /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode next = nu..

개념Interval은 구간 배열 or 리스트가 주어지며, 구간을 삽입, 삭제, 병합 하는 문제가 주어진다.  특징관련 문제 유형은 다음 세가지로 볼 수 있다.새로운 구간 하나를 구간들 사이에 넣기.구간들의 겹치는 부분을 정리하기.최대 겹치는 구간 길이 구하기.이때, 각 구간은 [시작점, 끝점]의 형식으로 시작점과 끝점이 배열로 정의되어 있다. interval 문제는 정렬이 중요하다.구간 배열이 intervals라고 하면 시작점이나 끝점을 기준으로 오름차순 정렬을 하는 것이 기본이다.// start 기준 오름차순 정렬Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]);// end 기준 오름차순 정렬Arrays.sort(intervals, (a,b) -..