[LeetCode] Palindrome Linked List

leetcode.com/explore/featured/card/top-interview-questions-easy/93/linked-list/772

Explore - LeetCode

주어진 Linked List 가 앞부터 읽었을때와 뒤에서 읽었을 때 값이 같은 지 리턴

[1, 2, 2, 1] ➡ true

[1, 2] ➡ false

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null){
            return true;
        }
        ListNode node = head;
        Stack<Integer> stack = new Stack<>();
        while(head.next != null){
            stack.push(head.val);
            head = head.next;
        }
        if (node.val != head.val){
            return false;
        }
        while (node.next != null){
            node = node.next;
            if (node.val != stack.pop()){
                return false;
            }
        }
        return true;
    }
}

1️⃣ 노드가 하나일 경우 true

2️⃣ 비교를 위한 ListNode 변수에 node 저장, 뒤에서 부터 꺼낸 노드 값 확인을 위해 Stack 변수 생성

3️⃣ 스택에 노드 순서대로 담는다 (꺼낼때는 뒤에부터 꺼내짐)

*️⃣ node의 값은 최초의 head를 담아두었고, while문을 돌린이후의 head.val은 마지막 노드의 값임

따라서 node.val (처음 노드 val)과 head.val (마지막 노드 val) 이 다르다면 false를 리턴한다. 두번째 노드부터 stack에서 하나씩 꺼내보며 비교하면서 다르면 false, 모두 꺼냈는데도 다른게 없으면 true를 리턴한다.