Java O(N)/O(1) solution


  • -1
    W
    /**
     * 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;
            ListNode fast=head;
            ListNode cur=head;
            ListNode newHead=head;
            ListNode node=head;
            while(fast.next!=null&&fast.next.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            if(fast.next==null){
                while(cur.next!=slow){
                    node=cur.next;
                    cur.next=cur.next.next;
                    node.next=newHead;
                    newHead=node;
                }
                cur.next=null;
                while(newHead!=null||slow.next!=null){
                    if(newHead==null&&slow.next!=null)return false;
                    if(newHead!=null&&slow.next==null)return false;
                    if(newHead.val!=slow.next.val){
                        return false;
                    }
                    newHead=newHead.next;
                    slow=slow.next;
                }
                return true;
            }else if(fast.next.next==null){
                ListNode newHead2=slow.next;
                while(cur.next!=newHead2){
                    node=cur.next;
                    cur.next=cur.next.next;
                    node.next=newHead;
                    newHead=node;
                }
                cur.next=null;
                while(newHead!=null||newHead2!=null){
                    if(newHead==null&&newHead2!=null)return false;
                    if(newHead!=null&&newHead2==null)return false;
                    if(newHead.val!=newHead2.val){
                        return false;
                    }
                    newHead=newHead.next;
                    newHead2=newHead2.next;
                }
                return true;
            }
            return true;
        }
    }

Log in to reply
 

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