Algorithm/Linked List
-
Linked List | Partition ListAlgorithm/Linked List 2021. 7. 19. 23:07
Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. 주어진 Linked List를 파티션 하라는 문제이다. Integer 값이 주어지는데, 이보다 작으면 순서대로 왼쪽에, 크거나 같으면 순서대로 오른쪽에 나열해서 새로운 Linked List를 리턴하는 문제이다. Dummy Node를 이용해서 손쉽게 풀 수 있다. /** * Definition for ..
-
Linked List | Swap Nodes in PairsAlgorithm/Linked List 2021. 7. 12. 15:45
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.) 2 노드씩 짝을 지어서, 순서를 바꾸라는 문제이다. 또한, 값을 변형하는것이 아닌, 노드의 위치를 바꾸라는 문제이다. 만약 노드의 갯수가 0개, 1개일 경우는 그대로 리턴해야하며, 노드 갯수가 홀수일 때, 마지막 노드는 그대로 둔다. 한번의 Trip만에 해결할 수 있는 방식이 떠올라 바로 코딩을 했다. 해법은 아래와 같다. class Solution { publi..
-
Linked List | Remove Nth Node From End of ListAlgorithm/Linked List 2021. 7. 11. 21:01
Given the head of a linked list, remove the nth node from the end of the list and return its head. 끝에서 N번째 노드를 지우라는 문제이다. 맨먼저 생각할 수 있는 가장 간단한 방법은, 끝까지 한번 여행을 한 후, 총 갯수를 알아내어 n번만큼 빼고 다시 가게 해서 그 노드를 지우는 방법이다. 하지만 이 방법은 최대 2N의 Travel을 해야한다. 이것 말고, 두개의 포인터를 사용해서 차이를 두고 loop을 도는 방식으로 접근하게되면 더 빠르게 찾아낼 수 있다. 처음에는, n만큼을 덜 가서, 그 전 노드에서 그 다다음 노드로 연결하는것이 복잡해 보였지만, dummy node를 맨 앞에 만들어두고, 어떠한 경우든지 (맨 첫번째나 맨..
-
Linked List | Flatten a Multilevel Doubly Linked ListAlgorithm/Linked List 2021. 5. 27. 10:16
You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below. Flatten the list so that all the nodes appear in a single-level, doubly li..
-
Linked List | Add Two Numbers IIAlgorithm/Linked List 2021. 5. 27. 02:25
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. 두 Linked List가 있는데, Singly Linked List이고, 더한 값을 Linked List로 리턴하라는 문제이다. 하지만 덧셈을..
-
Linked List | Odd Even Linked ListAlgorithm/Linked List 2021. 5. 24. 22:44
Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list. The first node is considered odd, and the second node is even, and so on. Note that the relative order inside both the even and odd groups should remain as it was in the input. Linked List가 주어졌을 때, 홀수번째 노드들과 짝수번째 노드들을 나누어서, 모든 홀수는 앞쪽에, 모든 짝..
-
Linked List | Swapping Nodes in a Linked ListAlgorithm/Linked List 2021. 5. 15. 20:14
You are given the head of a linked list, and an integer k. Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed). 앞에서 k번째, 그리고 뒤에서 k번째 노드의 값을 swap, 즉 바꾸라는 Medium 난이도의 문제이다. 아래와 같은 조건도 주었다. 노드의 값이 크지 않기때문에 swap하는것은 별로 큰 문제가 없겠지만, 총 리스트의 크기가 100,000 이기때문에 (컴퓨터에게는 그렇게 큰 숫자는 아니지만) 리스트를 travel 하는 숫자를 적게 하는..