Java O(n) time, O(1) Space


  • 1
    W
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head==null||head.next==null)return true;
            ListNode walker = head;
            ListNode pre = walker;
            ListNode runner = head;
            while(runner.next!=null && runner.next.next !=null){
                pre = walker;
                walker = walker.next;
                runner = runner.next.next;
            }
            ListNode head2 = walker.next;
            if(runner.next==null) pre.next=null;
            else walker.next = null;
            ListNode head1 = reverse(head);
            while(head1!=null){
                if(head1.val!=head2.val)return false;
                head1=head1.next;
                head2=head2.next;
            }
            return true;
        }
        public ListNode reverse(ListNode head){
            if(head==null||head.next==null)return head;
            ListNode prev = head;
            ListNode curr = head.next;
            ListNode next = curr.next;
            curr.next = prev;
            prev.next = null;
            prev = curr;
            curr = next;
            if(curr==null)return prev;
            while(curr!=null){
                next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }
    }

  • 0
    F

    Is it O(1) space?


  • 0
    L

    Yes, he only uses several pointers.


Log in to reply
 

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