Palindrome Linked List - LeetCode

1. 데크(Deque)를 이용한 풀이
   • 앞 뒤로 모두 추출할 수 있는 자료구조가 필여
   • 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는 데 시간 복잡도가 O(1)이 걸린다.
2. 러너를 활용한 풀이
   • 러너기법
     • 연결리스트 순회할 때 2개의 포인트를 동시에 사용하는 기법
     • 빠른 놈 = 2칸, 느린 놈 = 1칸씩 이동하는데 빠른놈이 리스트 끝에 도달하면 느린놈은 정확히 중 간 지점임
     • 중간 위치를 찾으면 리스트의 길이를 알아 낼 수 있음
     • 값을 비교하거나 뒤집기를 시도하는 등 활용할 수 있기 떄문에 반드시 알아야하는 기법임

하지만, 나는 러너 기법은 우선 어려운 것 같아 노드를 사용하는 기법으로 풀이를 학습함

public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public boolean isPalindrome(ListNode head) {
    Deque<Integer> deque = new LinkedList<>();

    ListNode node = head;
    while (node != null) {
        deque.add(node.val);
        node = node.next;
    }

    while(!deque.isEmpty() && deque.size() > 1) {
        if (deque.pollFirst() != deque.pollLast()) {
            return false;
        }
    }

    return true;
}