Find whether a LL is Pallindrome

bool isPallindrome(Node* head){
    // find middle element, reverse second half, check.
    int k = LLsize(head)/2;
    head = reverseAfterK(head, k);

    Node* p = head;
    Node* q = head;

    // q to k+1
    for(int i=1;i<=k;i++){
        q = q->next;
    }

    // check
    for(int i=1;i<=k;i++){
        if(p->data != q->datareturn false;
        p = p->next
        q = q->next;
    }
    return true;
}

Node* reverseAfterK(Node* &head, int k){
    // go to kth
    Node* temp = head;
    for(int i=1;i<k;i++){
        temp = temp->next;
    }

    if(temp->next == NULL || temp->next->next == NULLreturn head;

    Node* newTail = temp->next;

    // reversing
    Node* prev = NULL;
    Node* cur = temp->next;
    Node* nex = temp->next->next;

    while(cur){
        cur->next = prev;
        prev = cur;
        cur = nex;
        if(nex) nex = nex->next;
    }
    temp->next = prev;
    newTail->next = NULL;
    return head;
}


Comments

Popular Posts