반응형
//공통적으로 쓰이는 클래스
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
public static void printList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.print(current.val + "-> ");
current = current.next;
}
System.out.print("\n");
}
}
[ch8/P13] L234. 팰린드롬 연결 리스트
import java.util.Deque;
import java.util.LinkedList;
public class P13 extends ListNode{
P13(int val) {
super(val);
}
public static boolean isPalindrome(ListNode head) {
// 데크 선언
Deque<Integer> deque = new LinkedList<>();
// 연결 리스트의 값을 데크에 저장
ListNode current = head;
while (current != null) {
deque.addLast(current.val);
current = current.next;
}
// 양쪽에서 값을 하나씩 비교
while (deque.size() > 1) {
if (!deque.pollFirst().equals(deque.pollLast())) {
return false;
}
}
return true;
}
public static void main(String[] args) {
// 예제 사용법:
ListNode head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(2);
head1.next.next.next = new ListNode(1);
System.out.println(isPalindrome(head1)); // 출력: true
ListNode head2 = new ListNode(1);
head2.next = new ListNode(2);
System.out.println(isPalindrome(head2)); // 출력: false
}
}
[ch8/P14] L21. 두 정렬 리스트의 병합
public class P14 extends ListNode {
P14(int val) {
super(val);
}
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 기저 사례: 둘 중 하나가 비어 있으면 다른 리스트를 반환
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
// 현재 노드 값 비교
if (list1.val < list2.val) {
// list1의 값이 더 작은 경우
// list1의 다음 노드와 list2를 재귀적으로 병합
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
// list2의 값이 더 작거나 같은 경우
// list2의 다음 노드와 list1을 재귀적으로 병합
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
public static void main(String args[]) {
ListNode list1 = new ListNode(1);
list1.next = new ListNode(2);
list1.next.next = new ListNode(4);
ListNode list2 = new ListNode(1);
list2.next = new ListNode(3);
list2.next.next = new ListNode(4);
ListNode mergedList1 = mergeTwoLists(list1, list2);
printList(mergedList1);
}
}
반응형
'Portpolio > java_algo_interview' 카테고리의 다른 글
자바 알고리즘 인터뷰 10. 데크, 우선순위 큐 (0) | 2024.02.16 |
---|---|
자바 알고리즘 인터뷰 09. 스택, 큐 (0) | 2023.12.31 |
자바 알고리즘 인터뷰 07. 배열 (0) | 2023.12.31 |
자바 알고리즘 인터뷰 06. 문자열 처리 (0) | 2023.12.31 |
자바 알고리즘 인터뷰 05. 빅오 표기법 (2) | 2023.12.26 |
댓글