Leetcode 234. Palindrome Linked List

문제 이해

- 링크드 리스트가 팰린드롬인지 아닌지 판별하라 

 

해결 전략

- 이 문제를 푸는데는 여러 가지 전략이 있습니다.

-> 그 중에서 '뒤집어서 비교하는' 전략을 선택했습니다.

- reverseAndClone 메소드를 통해서 뒤집은 ListNode를 만들고,

  isEqual 메소드를 통해서 비교해줍니다. 

 

구현

class Solution {
    
    
    public ListNode reverseAndClone(ListNode node){
        
        ListNode head = null;
        
        while(node != null){
            ListNode n = new ListNode(node.val);
            n.next = head;
            head = n;
            node = node.next;
        }
        
        return head;
        
    }
    
    
    
    public boolean isPalindrome(ListNode head) {
        
        ListNode reversed = reverseAndClone(head);
        return isEqual(head, reversed);    
        
    }
    
    
    public boolean isEqual(ListNode one, ListNode two){
        
        
        while(one != null && two != null){
            if(one.val != two.val){
                return false;
            }
            one = one.next;
            two = two.next;
        }
        
        return one == null && two == null;
    }
    
    
    
}

 

피드백

- 링크드 리스트를 뒤집는 방법을 알아야 합니다.