234. Palindrome Linked List(Linked List, Stack, Two Pointers, Recursion)*

문제

Given the head of a singly linked list, return true if it is a
palindrome or false otherwise.

https://leetcode.com/problems/palindrome-linked-list/description/

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

풀이

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

        // while(head!=null){
        //     if(head.val!=stack.pop()) return false;
        //     head=head.next;
        // }

        // return true;
        
        //역방향
        ListNode newHead = reverseNode(head);

       while(head!=null){
           if(head.val!=newHead.val) return false;
           head = head.next;
           newHead = newHead.next;
       }
       return true;
    }

    public ListNode reverseNode(ListNode head){
        ListNode current = head; 
        ListNode newHead = new ListNode(0);
        while(current!=null){
            ListNode next = new ListNode(current.val);
            next.next = newHead.next;
            newHead.next = next;
            current = current.next;
        }
        return newHead.next;
    }
}