O(n) time and O(1) space C++ solution


  • 2
    Y
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {//O(n) time and O(1) space solution
    public:
        bool isPalindrome(ListNode* head) {
            if(!head || !head -> next) return true;
            ListNode* fast = head,*slow = head; //fast and slow pointer to find the middle position
            while(fast && fast -> next) {
                slow = slow -> next;
                fast = fast -> next -> next;
            }
            if(fast) slow = reverseList(slow -> next);//reverse the last half of the list
            else slow = reverseList(slow);
            while(slow) {
                if(head -> val != slow -> val) return false;
                head = head -> next;
                slow = slow -> next;
            }
            return true;
        }
        ListNode* reverseList(ListNode* head) {
            if(!head) return NULL;
            if(!head -> next) return head;
            ListNode* pre = head -> next;
            head -> next = NULL;
            ListNode* temp;
            while(pre) {
                temp = pre -> next;
                pre -> next = head;
                head = pre;
                pre = temp;
            }
            return head;
        }
    };

Log in to reply
 

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