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


  • 0
    W
    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.