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->data) return 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 == NULL) return 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
Post a Comment