자바 알고리즘 인터뷰 08. 연결 리스트

//공통적으로 쓰이는 클래스
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);
    }

}