O(n) time and O(1) space 4ms java solution


  • 0
    S
    public class Solution {
        public boolean isPalindrome(ListNode head) {
           if(head == null || head.next == null){
               return true;
           }
           ListNode slow = head;
           ListNode fast = head;
           while(fast != null && fast.next != null){
               slow = slow.next;
               fast = fast.next.next;
           }
           if(fast != null && fast.next == null){
               slow = slow.next;
           }
           fast = head;
           ListNode rest = reverse(slow);
           slow.next  = null;
           while(fast != null && rest != null){
               if(fast.val != rest.val){
                   return false;
               }
               fast = fast.next;
               rest = rest.next;
           }
           return true;
        }
        
        private ListNode reverse(ListNode head){
            if(head == null || head.next == null){
                return head;
            }
            ListNode rest = reverse(head.next);
            head.next.next = head;
            head.next = null;
            return rest;
        }
    }
    

  • 0
    Z

    Great solution! Yet it seems like the original linked list would not be a legal linked list anymore after the reverse() method, since that there will be 2 different objects both point to the last element of the newly reversed list. It would not do harm to the result of this question, yet it sounds kind of uncomfortable. I change it a little bit, by adding a node slow_prev pointing to the previous node of slow. Then I make slow_prev point to the last element of the former list before reversing. Here is my code:

    /**
     * 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 fast = head, slow = head, slow_prev = head;
            int cnt = 1;
            fast = fast.next.next;
            slow = slow.next;
            while (fast != null && fast.next != null)
            {
                fast = fast.next.next;
                slow = slow.next;
                slow_prev = slow_prev.next;
                cnt++;
            }
            fast = head;
            slow = f(slow);
            slow_prev.next = slow;
            while (cnt > 0)
            {
                if (fast.val != slow.val) return false;
                fast = fast.next;
                slow = slow.next;
                cnt--;
            }
            return true;
        }
        private ListNode f(ListNode node)
        {
            if (node.next == null) return node; // one node left
            ListNode last = f(node.next);
            node.next.next = node;
            node.next = null;
            return last;
        }
    }
    

Log in to reply
 

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