My very easy understanding Java solution O(n)


  • 0
    J
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null) return true;
            //get the node in the middle using slow and fast pointers
            ListNode slow = head;
            ListNode fast = head;
            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            //count the # of nodes if odd move slow pointer one step
            int n = 0;
            ListNode temp = head;
            while(temp != null){
                n++;
                temp = temp.next;
            }
            if(n%2 == 1) slow = slow.next;
            //reverse the second half list 
            ListNode pre = null;
            ListNode cur = slow;
            ListNode next = null;
            while(cur != null){
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            //compare pre with head until pre = null
            while(pre != null){
                if(pre.val == head.val){
                    pre = pre.next;
                    head = head.next;
                }else break;
            }
            if(pre == null) return true;
            else return false;
        }
    }

  • 0
    L

    it's a bad solution because you modified the original list


Log in to reply
 

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