Share My O(n) O(1) Java Solution


  • 1
    A
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head==null || head.next==null) return true;
            ListNode slow = head;
            ListNode fast = head;
            while(fast.next!=null && fast.next.next!=null){
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode next = slow.next.next;
            ListNode tail = slow.next;
    
            //Invert half list   
            while(next!=null){
                ListNode temp = slow.next;
                slow.next = next;
                tail.next = next.next;
                next.next = temp;
                next = tail.next;
            }
    
            while(slow.next!=null){
                if(head.val != slow.next.val){
                    return false;
                }
                slow = slow.next;
                head = head.next;
            }
            return true;
        }
    }

  • 0
    M

    /**

    • 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) {
      if(head == null || head.next == null){
      return true;
      }

       ListNode slow = head, fast = head;
       
       while(fast.next != null && fast.next.next != null){
           fast = fast.next.next;
           slow = slow.next;
       }
       
       ListNode newHead = reverseList(slow);
       
       while(newHead.next != null){
           if (head.val != newHead.val){
               return false;
           }
           head = head.next;
           newHead = newHead.next;
       }
       return true;
      

      }

      private ListNode reverseList(ListNode head) {
      ListNode prev = null;
      ListNode cur = head;

       while(cur != null){
           ListNode originalNext = cur.next;
           cur.next = prev;
           prev = cur;
           cur = originalNext;
       }
       return prev;
      

      }
      }


Log in to reply
 

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