[자바] Leetcode 234 - Palindrome Linked List

• 최적화된 방법은 아니다. 일단 Linked List를 끝까지 타면서 ArrayList<Integer> list에 담아주고, 그 list의 양 끝값들을 하나씩 비교해가면서 어긋나는 게 있으면 바로 answer = false를 넣고 나와버린다. 
• Linked List를 순회하는데 걸리는 시간 O(n) + ArrayList의 절반을 순회하는데 걸리는 시간 O(n/2)해서 결국 대략 O(n)이기는 한데, 성능이 하위 70%에 속한다 ㅎ

• 시간이 빠른 다른 풀이를 보면 두 개의 변수 (fast, slow)를 써서 뭔가를 하는 것 같은데, 이해는 나중에 해야겠다!

---

• 처음 제출했을 때, [-129, -129] 케이스에서 Wrong Answer가 나왔다. 일단 잘못 생각했던 점은, 자바를 너무 겉핥기 식으로 했어서 그런지 Integer도 객체라는 사실을 깜빡하고 바로 그냥 == 연산자로 비교해버린 것! intValue() 메소드를 사용해서 주소값이 아닌 실제 값을 비교해줘야 한다. 

 

• 근데 아무리 생각해도 이상했다. 왜 다른 케이스들은 맞았지..?  그래서 찾아보니까 아래 내용에서 답을 얻었다. IntegerCache 클래스에서 ~128부터 127까지는 auto-boxing이 되도록 관리를 해준다고 한다! 그러니 딱 -129에서는 에러가 났지만, 다른 케이스에서는 에러가 안 난 것! 

meetup.toast.com/posts/185

[Java] Integer.valueOf(127) == Integer.valueOf(127) 는 참일까요? : NHN Cloud Meetup

---

• 전체 코드는 아래와 같다.

 

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        boolean answer = true;
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        ListNode node = head;
        while(node!=null){
            list.add(node.val);
            node = node.next;
        }
        
        int len = list.size();
        for(int i=0;i<(len/2);i++){
            
            if(list.get(i).intValue() != list.get(len-i-1).intValue()){
                answer = false;
                break;
            }
        }
        return answer;
    }
}