234. Palindrome Linked List!

/**
 * 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) {
        ListNode[] lists = divideList(head);
        // if list[1] is null, there is only 1 element in the input list
        if(lists[1]==null) return true;
        
        ListNode l1=lists[0];
        ListNode l2=reverseList(lists[1]);
        
        //compare elements in the two lists
        while(l1!=null && l2!=null){
            if(l1.val!=l2.val) return false;
            l1=l1.next;
            l2=l2.next;
        }
        return true;
    }
    
    //head should not be null
    private ListNode[] divideList(ListNode head){
        ListNode[] lists = new ListNode[2];
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null && fast.next.next!=null){
            slow=slow.next;
            fast = fast.next.next;
        }
        lists[0] = head;
        lists[1] = slow.next;
        //separate the list
        slow.next = null;
        return lists;
    }
    
    // head cannot be null
    private ListNode reverseList(ListNode head){
        ListNode first=null;
        ListNode second = head;
        ListNode third = head.next;
        while(second!=null){
            second.next=first;
            first = second;
            second = third;
            if(third!=null) third=third.next;
        }
        return first;
    }
}