예시1을 보면 문제 이해가 쉬운데, 두개의 Linked List가 인풋으로 들어오면, 각각 순서를 바꿔서 저장한 후 int로 만들어 이를 더한다. 더한 값을 다시 Linked List로 만드는데, 얘 역시 거꾸로 만든다 이 문제는 reverse연산인데, 원래 942+476으로 연산해야 할 input이 거꾸로 들어온다. 그렇다면 들어온 리스트 순서 그대로 연산한다면 어떤 부분을 고려해야 할까? 자릿수대로 더해주고 결과 linked list에 거꾸로 집어넣으면 된다. 그런데 문제는 두 노드의 합이 10이 넘어가는 경우다 10이 넘어가면 1을 다음 자릿수로 넘겨준다. 따라서 이 문제의 index는 4개가 필요하다. List를 만들고 우리는 List.next를 결과로 리턴해줄것이다. 이 List에는 연산값이 담..

Linked List를 오름차순으로 정렬하라는 문제이다. 공간복잡도가 O(1)이라 최대한 해당 리스트내에서 sort해보겠다 일단 경계값을 제외한다 이후 메인로직에 서는 Merge Sort를 이용한다 분할-> 합병의 순서로 배열을 처리한다. 분할의 경우 반으로 쪼갠다. 보통 Array를 정렬하는 경우 반으로 나누면 되는데, Linked List는 길이를 알 수 없으므로 fast와 slow라는 노드를 두고, slow는 한칸, fast는 두칸씩 움직이면 fast가 끝나는 시점에서 딱 반절의 위치를 알수 있게 된다. 이를 재귀로 길이가 0또는 1이 될때까지 쪼갠다. 이때 prev는 이전 함수에서 사용한 인덱스이므로 next를 null로 설정해주어야 한다. 분할이 끝나면 합병을 진행한다 재귀를 통해 0또는 1길이..

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: 연결된 두개의 Linked List에서 Intersection 노드를 찾는 문제이다 이러한 경우 two pointer를 응용하면 된다 예를들어 input : listA = [0,9,1,2,4], listB = [3,2,4]라면 listA: 0 -> 9 -> 1 listB: 3 -> 2 -> 4 순서로 순회할것이다 여기부터 listB.next는 none이 된다. 이 경우 다시 얘를 listA의 첫번째 head node로 이어주자 listA: 0 -> 9 -> 1..

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 of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter. Return true if there is a cycle..

Given a singly linked list, determine if it is a palindrome. palindrome은 대칭이란다 즉, Linked List가 거꾸로 들어와도 동일하게 대칭되는 List인지 여부를 묻는 문제 사실 시간,공간 복잡도가 중요한 문제라, 어떻게 하면 Loop 한개로 풀지 고민했다 이 경우 정방향으로 먼저 Loop를 돌면서 value를 배열에 저장해두고, Loop를 역방향으로 한번 더 돌면서 정방향과 짝지를 이루는지 점검해보면 된다.

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 문제에서 항상 기억할 점은 1) 첫 input은 Head Node이다 2) 우리가 받는 input은 Head Node와 Tail Node(next 메소드로 얻어낼 수 있는) 뿐이다 3) 따라서 유연한 조작을 위해 index가 필요하다 라는 부분이다 내 풀이는 다음과 같다 이를 도식화시키면 다음과 같은데 차근차근 설명해보면 결과값이 될 List를 만들고, 그 List의 객체를 만든다. 얘가 인덱스 노드가 된다. 우리는 인덱스 노드에 적절..