Easy and Readable Java solution - accepted.


  • 0
    A

    /**

    • Definition for singly-linked list.

    • public class ListNode {

    • int val;
      
    • ListNode next;
      
    • ListNode(int x) { val = x; }
      
    • }
      */
      public class Solution {
      public boolean isPalindrome(ListNode head) {
      // Make sure the list is valid
      if(head == null || head.next == null){
      return true;
      }

       //find length
       int length = 0;
       ListNode start = head;
       while(start != null){
           length += 1;
           start = start.next;
       }
       
       // If length is exactly two, don't spend time reversing- compare directly
       if(length == 2){
           return (head.val == head.next.val);
       }
       
       // Reverse list upto half length;
       start = head;
       int k = 0;
       ListNode ahead = start.next; ListNode prev = null; 
       ListNode newHead = null;ListNode restHead = null;
       /** After reversing the new head will be head of the reverse point
            rest head will be the head of the not reversed point. */
       //For eg: 1->2->2->1 - will become (newHead) 2->1 and (restHead) 2->1.
       //To make sure we reverse the right number of links we do (l-1)/2 
       
       while(k < (length-1)/2){
           start.next = prev;
           ListNode temp = ahead.next;
           ahead.next = start;
           prev = start;
           start = ahead;
           newHead = ahead;
           ahead = temp;
           restHead = ahead;
           k += 1;
       }
       
       //fast pointer and slow pointer
       k = 0; ListNode fp = restHead; ListNode sp = newHead;
       
       // If list is odd in number then don't consider the middle element.
       if(length %2 != 0){
           sp = sp.next;
       }
       // Compare the two lists in a same way
       while(fp != null && sp != null){
           if(sp.val != fp.val){
               return false;
           } sp = sp.next; fp = fp.next;
       }
       return true;
      

      }
      }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.