Algorithm/Linked List
-
Linked List | Merge In Between Linked ListsAlgorithm/Linked List 2021. 5. 13. 23:29
You are given two linked lists: list1 and list2 of sizes n and m respectively. Remove list1's nodes from the ath node to the bth node, and put list2 in their place. Medium 난이도의 문제이다. 두 Linked List가 주어졌을 때, list1의 a번부터 b를 삭제한 후, 삭제된 자리에 list2를 넣는 문제이다. O(N)으로 해결하기 위해 아래와 같이 접근했다. class Solution { public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) { ListNode temp = null; ..
-
Linked List | Remove Duplicates from Sorted ListAlgorithm/Linked List 2021. 5. 2. 21:07
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well. 이미 숫자로 정렬되어있는 Linked List에서 중복되는 값을 가진 노드들을 삭제한 후, 다시 Linked List를 리턴하라는 문제이다. 리턴시에는 그 리스트의 Head를 리턴하면 된다. 이 문제는 한번의 loop으로 해결할 수 있다. class Solution { public ListNode deleteDuplicates(ListNode head) { if(head == null) return null; ListNode pivot = head; L..
-
Linked List | Merge Two Sorted ListsAlgorithm/Linked List 2021. 5. 2. 17:11
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists. 두 Linked List를 Merge하라는 문제이다. 두 리스트 모두 이미 순서대로 (작은숫자부터 큰숫자로) 정렬되어있다. 가장 단순한 방법은, 비교를 해가면서 새로운 리스트에 값을 복사하는 방법이 있을 것 같은데, 메모리를 조금 아끼려면, 주어진 Linked List자체를 변형하는 방법이 있다. class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode tempHe..
-
Linked List | Reverse Linked ListAlgorithm/Linked List 2021. 4. 29. 23:27
Given the head of a singly linked list, reverse the list, and return the reversed list. 말 그대로, head노드를 가지고 Linked List를 reverse해서, 새로운 head를 리턴하는 문제다. 모두 오른쪽을 바라보다가, 순차적으로 왼쪽을 바라보게 하는 그림을 연상시킨다. 이 문제를 한큐만에, O(N)으로 푸는 방법이 있다. 바로 지나가면서 뒤집는 방법이다. 코드는 다음과 같다. class Solution { public ListNode reverseList(ListNode head) { ListNode newNext = null; ListNode temp = null; ListNode curr = head; while(curr ..
-
Linked List | Delete Node in a Linked ListAlgorithm/Linked List 2021. 4. 28. 22:52
Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly. It is guaranteed that the node to be deleted is not a tail node in the list. Constraints: * The number of the nodes in the given list is in the range [2, 1000]. * -1000
-
Linked List | Middle of the Linked ListAlgorithm/Linked List 2021. 4. 27. 23:16
Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node. LinkedList에서 가운데에 있는 Node를 리턴하라는 문제이다. 처음 접근은 1.5N의 loop을 돌리는 방식이었다. class Solution { public ListNode middleNode(ListNode head) { int count = 0; ListNode curr = head; while(curr != null){ curr = curr.next; count++; } curr = head; count = co..
-
Linked List | Convert Binary Number in a Linked List to IntegerAlgorithm/Linked List 2021. 4. 26. 23:41
Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number. Return the decimal value of the number in the linked list. Linked List에 binary 값이 들어가있고 (0 또는 1), 그 값을 integer값으로 계산하는 조건의 문제이다. 처음에는 O(N)이지만, 실제로는 2N, 그러니까 Loop을 두번 도는 알고리즘을 구현했다. Linked List에서는 Easy 난이도의 문제이다. cla..