[Easy] 234. Palindrome Linked List

Leetcode 234번 문제는 주어진 linkedlist 가 palindrome(회문) 인지 아닌지 판단하는 문제이다. 여기서 palindrome은 거꾸로 읽어도 똑바로 읽어도 같은 문자열이다. 예)기러기, 토마토, 스위스, 인도인, 별똥별, 우영우. 

 

#ArrayList 사용법

class Solution {
    public boolean isPalindrome(ListNode head) {
       ArrayList<Integer> al = new ArrayList<Integer>();
        ListNode current = head;
        while(current !=null){
            al.add(current.val);
            current = current.next;
        }
        int i = 0, j = al.size() - 1;
        
        while(i < j){
            if(al.get(i) != al.get(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

linked list 를 traverse해 모든 값을 arraylist에 담아 arraylist의 처음과 끝부터 시작해서 비교하는 방식이다.

 

# floyd's tortoise and hare algorithm 플로이드의 토끼와 거북이 알고리즘

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head, prev, temp;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        prev = slow;
        slow = slow.next;
        prev.next = null;
        while (slow != null) {
            temp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = temp;
        }
        fast = head;
        slow = prev;
        while (slow != null) {
            if (fast.val != slow.val) return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
}