moonscode

/** * [회문] * 주어진 연결리스트가 회문인지 검사하는 함수를 작성 * * [풀이] * => 리스트 내부함수로 구현하는가 ? * => 양방향인가 단방향인가 ? * => 전체 길이를 캐싱할 수 있는가 ? * */ public class Q06 { public static void main(String[] args) { } /* Node */ static class Node { Node next; int data; Node(int data) { this.data = data; } } /* isPalindromeA */ static boolean isPalindromeA(Node head) { Node reversed = reverseAndClone(head); return isEqual(head, re..

/** * [리스트의합] * 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로표현할 수 있다. * 각 숫자는 역순으로 배열되어 있는데 첫번째 자릿수가 리스트의 맨 앞에 위치하게 배열된다는 뜻이다. * 이와 같은 방식을 표현된 숫자 두개가 있을 때 이 두수를 더해 그 합을 연결 리스트로 반환하는 함수를 작성 * * [풀이] * => 리스트를 직접구현 ? * => 최대 혹은 최소 몇자리수까지 리스트가 존재하는가 ? * * */ public class Q05 { public static void main(String[] args) { sumList(Arrays.asList(9, 9, 9), Arrays.asList(9, 9, 9)); // 1998 } /* sumList - 외부구현 *..

/** * [분할] * 값 x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들 보다 앞에 오도록 하는 코드를 작성 * 만약 x가 리스트에 있다면 x는 그보다 작은 원소들 보다 뒤에 나오기만 하면 된다. * 즉, 원소 x는 오른쪽그룹 어딘가에 존재하면 된다. 왼쪽과 오른쪽 사이에 있을 필요는 없다. * * [예제] * (3) > [5] > 8 > [5] > 10 > (2) > (1) [분할5] * 3 > 1 > 2 > 10 > 5 > 5 > 8 * * [풀이] * => 요청받은 분할값 뒤로 분할값보다 작은게 있으면 앞으로 보내면 된다. * * */ public class Q04 { class Node { Node next; int data; } /* partitionA - 두개의 리스트를 만..

/** * [중간노드삭제] * 단방향 연결리스트가 주어졌을때 중간(처음과 끝이 아님)에 있는 노드 하나를 삭제하는 알고리즘을 구현해라 * 단 삭제할 노드에만 접근할 수 있다. * * Poinst. * => 리스트 내부함수 ? 외부함수 ? * => 삭제는 인덱스로 ? 객체로 ? * * */ public class Q03 { class Node { Node next; int data; } class MyList { Node head; MyList() { } // == 노드 기준 (O) - 마지막 노드를 삭제할 수 없음 == boolean delete(Node node) { Node next = node.next; node.data = next.data; node.next = next.next; return ..

/** * [뒤에서 k번째 원소 구하기] * 단방향 연결리스트가 주어졌을 때 뒤에서 k 번째 원소를 찾는 알고리즘을 구현 * * [풀이] * => 전체길이를 캐싱하고 있는가 ? * => 전체길이를 구하고 재차 뒤에서 K번째를 구함 * */ public class Q02 { public static void main(String[] args) { } /* Node */ static class Node { Node next; int data; Node(int data) { this.data = data; } } /* getNodeFromRear */ static Node getNodeFromRear(Node head, int k) { if(head == null) return null; Node node =..

/** * [중복없애기] * 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성 * 임시버퍼를 사용하지 않고 만들수 있을까? * * [풀이] * => 리스트의 내부구현인가 ? 외부구현인가 ? * => 외부구현일때, 주어진 리스트를 사용해도 되나 ? * => List Iterater 활용 * => Set 으로 데이터 임시저장 * */ public class Q01 { public static void main(String[] args) { List list = new LinkedList(); list.add(1); list.add(1); list.add(2); list.add(2); list.add(3); list.add(3); deleteDuplicationA..