My O(n) time, O(1) space C solution 12ms


  • 1
    T
    bool isPalindrome(struct ListNode* head) {
      
        struct ListNode* slow=head;
        struct ListNode* fast=head;
        struct ListNode* aux=NULL;
        while(fast&&fast->next){
            struct ListNode* temp=slow;
            slow=slow->next;
            fast=fast->next->next;
            temp->next=aux;
            aux=temp;
        }
        if(fast)
            slow=slow->next; 
        while(slow&&aux->val==slow->val){
            aux=aux->next;
            slow=slow->next;
        }
        return slow==NULL;
        
    }

  • 0
    A

    Coincise code, but could you explain briefly the idea under it?


  • 1
    T

    Sorry for not commenting out my code.

    The basic idea is use two pointer method to find the center of the linked list. While slow pointer goes down the linked list, a temp pointer and aux pointer are also used to switch the direction of the linked list for later comparison. aux will be the head of the first half linked list after the first while loop ends. The if statement following the first while loop takes care of odd number of list nodes case. The second while loop just check whether the first half is the same as second half. For the return statement, if it is a palindrome, slow will point to null, return true; if it is not a palindrome, it will point to non-null node, giving false back.

    Hope this helps.


  • 0
    A

    After reading the above explanation, I find the idea of one of my algorithms is the same as yours. But your code is a little more efficient than mine, as yours can find the middle by walking through the linked list only once (two pointers), but mine needs twice with only one pointer. Your code is a good inspire to me. Thank you.


  • 0
    F

    Sorry, I have some questions about the order of the code:
    '''
    bool isPalindrome(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode * tmp = slow;
    struct ListNode* aux = NULL;
    while(fast&&fast->next){
    tmp = slow;
    slow = slow->next;
    fast = fast->next->next;
    tmp->next = aux;
    aux = tmp;
    //fast = fast->next->next;
    }
    if(fast)
    slow = slow->next;
    while(slow&&aux->val==slow->val){
    slow = slow->next;
    aux = aux->next;
    }
    return slow==NULL;
    }
    '''
    if I change the position of the fast = fast->next->next; to the //fast = fast->next->next;
    the answer would be runtime error, could you help me why? QQ


  • 0
    T

    @frank9810002
    The first while loop is doing two pointer advance and linked list reverse at the same time. If you use your suggested way, during the first time execution of the while loop, the head of the linked list is already disconnected from the rest of the list. But, fast pointer is still on the head. So, fast->next->next is pointing to nothing which causes the error.


  • 0
    F

    @terrific1985 Thanks a lot !!!!!


Log in to reply
 

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