Linked List4 Blind 75 | Remove Nth Node From End of List (Linked List 5 / 6) 알고리즘 브루트포스 연결 리스트의 처음부터 끝까지 한번 순회해서 길이를 구하고 그 길이를 이용해서 Nth 노드를 없앤다. 구현은 쉽지만 리스트의 길이가 1이거나 2이거나 등의 엣지 케이스가 괴롭힌다. 더미 노드 슬라이딩 윈도우와 비슷한 기법으로 엣지 케이스들을 없앨 수 있다. 1. Dummy 노드를 생성한 후 root에 연결한다. 2. left, right 포인터를 만들고 right은 root, left는 Dummy 노드를 가리킨다. 3. right은 n만큼 오른쪽으로 이동한다. 4. 그 후 right 포인터가 null일 때까지 이동시키는데 이때 left 포인터도 같이 한 칸씩 이동한다. 5. right 포인터가 null일 때 left는 삭제해야 할 노드의 바로 전 노드를 가리키고 있는다. 그 노드의 n.. 2023. 6. 22. Blind 75 | Reorder List (Linked List 4 / 6) 연결리스트 뒷부분에서 시작되는 노드들을 앞에서부터 번갈아가며 연결하는 문제로 노드의 val을 임의로 수정하면 안 되고 어떠한 리턴도 하지 않는 함수를 작성해야 한다. 뒷부분에서 거꾸로 연결해 야하기 때문에 reverse linked list를 풀 수 있어야 이 문제를 풀 수 있다. 알고리즘 1. slow fast 포인터를 이용하여 노드의 중간 지점을 찾는다. 2. 중간 지점의 다음 노드부터 시작하여 연결 리스트를 거꾸로 연결한다. 3. 두 연결 리스트를 교차하며 연결한다. 구현 중간 지점을 찾는 첫번째 부분에서는 종이에 그림을 적어 그려 구현하면 더 쉽다. 두 번째 반을 거꾸로 만드는 작업에서 제일 중요한 부분은 두 번째 반 연결 리스트가 시작되기 직전의 노드의 next를 null로 만들어 한 개의 연결.. 2023. 6. 21. Blind 75 | Linked List Cycle (Linked List 3 / 6) https://leetcode.com/problems/linked-list-cycle/ Linked List Cycle - LeetCode Can you solve this real interview question? Linked List Cycle - Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuo leetcode.com Linked List Cycle 풀이 연결 리스트의 사이클을 체크하는 문제로 제일 간단한 .. 2023. 6. 20. Blind 75 | Merge Two Sorted Lists (Linked List 2 / 6) https://leetcode.com/problems/merge-two-sorted-lists Merge Two Sorted Lists - LeetCode Can you solve this real interview question? Merge Two Sorted Lists - You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists leetcode.com Merge Two Sorted Lists 풀이 재귀를 이용하면 쉽게 풀 수.. 2023. 6. 17. 이전 1 다음
