매일 조금씩

처음엔 Stack이나 Deque로 풀어야하나 했지만, 공간복잡도가 O(N)이 나올것이기 때문에,좀더 효율적인 방법을 생각해야했다. 투 포인터를 사용하면 공간복잡도 O(1)로 문제를 해결할 수 있다.문제의 핵심은 다음과 같다.순방향과 역방향이 둘다 존재한다.그림으로 그려보았을 때, 리스트의 앞쪽 절반은 순반향, 뒤쪽 절반은 역방향이다.따라서, 다음과 같은 순서로 알고리즘을 진행한다.리스트의 중간 노드를 찾는다. (slow, fast 포인터를 사용. 이때, slow는 중간에 도달한다. 뒤쪽 절반의 첫 번째 노드)리스트 후반부를 역순으로 뒤집는다. (prev는 역순 리스트의 첫번째 노드. 즉, 원래 리스트의 마지막 노드)두 리스트 병합 (앞쪽 노드 next를 뒤쪽 노드로, 뒤쪽 노드 next를 앞쪽 노드로, ..

두개의 포인터를 사용하는 것이 포인트다.초반엔 스택을 사용해서 푸는 방법을 생각했는데 그러다 보니 어차피 사라질 노드를 타겟으로 잡게되어서 고려해야할 상황들이 너무많았다.두개의 포인터를 다음과 같은 용도로 사용한다. 첫번째 포인터: 삭제될 노드와 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..