BytePudding

Stack은 추상자료형(Abstract Data Type , ADT)이기 때문에 구현 방법을 따로 명시하지 않아 어떤 방법으로든 구현이 가능하다. 보통 Array, LinkedList, Deque 중에서 사용하는데, 이 글은 LinkedList를 통해 Stack을 구현하는 방법을 소개한다. Stack 자료구조란? Stack 자료구조를 tail이 없는 LinkedList라고 생각하면 쉽다. LinkedList에서는 head를 제외하면 포인터를 이용해 노드에 접근하기 때문에 중간 노드로의 바로 접근이 불가하다. Stack도 이와 마찬가지로 중간으로의 접근이 불가하고 항상 LinkedList의 head에 해당하는 top에서만 접근이 가능하다. 그림으로 표현하면 아래와 같다. Stack은 그림과 같이 접시처럼 ..

중복값이 나오면 포인터를 리스트에서 빼는 문제이다. 요소를 Set 자료구조에 넣은 후,Set자료구조에 포함되면 이전포인터가 현재포인터를 건너띄고 다음포인터를 향하도록 하였다. 자바인데 컴파일러를 C로 했더니 계속 오류가 낫다 -- # Description 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. Example 1: Input: head = [1,1,2] Output: [1,2] Example 2: Input: head = [1,1,2,3,3] Output: [1,2,3] #Solution cl..

두시간이나 걸린 문제 .. x보다 작으면 앞에다가 옮기고, x보다 크면 뒤에다가 옮기는 문제다. 노드의 순서는 그대로 유지한 상태여야한다. dummy 노드 두개를 만들어서 x보다 작으면 dummy1에다 넣고 , x보다 크면 dummy2에다 넣은 후 둘이 합치면 된다. #Description 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. Examp..

마지막 노드부터 시작하여 인자값으로 주어진 노드를 빼고 head를 리턴하는 문제이다. # Description Given the head of a linked list, remove the nth node from the end of the list and return its head. Example 1: Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Example 2: Input: head = [1], n = 1 Output: [] Example 3: Input: head = [1,2], n = 1 Output: [1] #Solution class Solution{ public ListNode removeNthFromEnd(ListNode head,int n..

이번 문제는 LinkedList에 사이클(Cycle)이 있는지 판단하는 문제이며, 미국 신입개발자들 인터뷰에 많이 나온 문제라고 한다. 이번 문제도 slow와 fast 포인터를 이용하여 쉽게 풀 수 있었다. # Description 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 continuously following the next pointer. Internally, pos is used to denote the index..

LinkedList의 중간 노드를 찾는 문제인데 미국 신입개발자들 인터뷰에 많이 나온 문제라고 한다. 플로이드의 토끼와 거북이(Floyd Tortoise and Hare) 알고리즘으로 풀었다. # Description Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node. # Example 1 Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3. # Example 2 Input: head =..

이 글은 java.util. LinkedList 를 공부하면서 중요하다고 생각되는 메소드를 정리하였다. 1. Constructor public class LinkedList{ private Node head; //첫번째 노드 private Node tail; //마지막 노드 private int length; //노드의 수 class Node{ // Linked List 내부에 Node가 nested 클래스로 들어있음 int value; // 데이터 Node next;// 포인터 Node(int value){ // Node생성자 , 데이터를 파라메터로 받음 this.value = value; } } public LinkedList(int value){ // LinkedList의 생성자 Node newNo..