Share my c code which is 20 lines and 12 ms in O(n) and O(1)

  • 0
    bool isPalindrome(struct ListNode* head) {
        if(!head) return 1;
        int num = 0;
        struct ListNode* tnode,*pre,*next;
        pre = NULL;
        for(tnode = head;tnode != NULL; tnode = tnode->next,++ num);
        tnode = head;
        for(int i = 0;i < num / 2;++ i){
            next = tnode->next;
            tnode->next = pre;
            pre = tnode;
            tnode = next;
        if(num & 1) next = tnode->next;
        while(pre != NULL){
            if(pre->val != next->val) return 0;
            pre = pre->next;
            next = next->next;
        return 1;

    Just get the number of nodes and change the "next" pointer of nodes in first half of the list from the next one to the pre one. After that we can check every item from the middle of the list. And you can solve if in O(n) and O(1)
    For Chinese:

Log in to reply

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