本文實例講述了C++判斷一個鏈表是否為回文結構的方法。分享給大家供大家參考，具體如下：
題目：
給定一個鏈表頭節(jié)點head，請判斷是否為回文結構
例如：
1->2->1 true
1->2->2->1 true
1->2->3->4->2->1 false
解題思路及代碼
1、找到鏈表中間節(jié)點，然后將鏈表中間節(jié)點的右邊所有節(jié)點放入一個棧中。
2、然后從鏈表首節(jié)點和棧頂元素一一對比，不相等則return false。
算法C++代碼：
鏈表節(jié)點結構定義
typedef struct Node{ int data; struct Node* next;}node, *pLinkedList;bool isHuiWen(pLinkedList head){ if (head == NULL || head->next == NULL) return true; pLinkedList right = head->next;//保存中間節(jié)點的下一個節(jié)點(若為偶數(shù)則為偏右的中間節(jié)點) pLinkedList cur = head; //快指針 while (cur->next != NULL && cur->next->next != NULL) { right = right->next; cur = cur->next->next; } //當鏈表總結點個數(shù)為奇數(shù)情況時： if (cur->next != NULL && cur->next->next == NULL) right = right->next; //將鏈表右邊的節(jié)點放入一個棧中 stack<pLinkedList>* s = new stack<pLinkedList>(); while (right != NULL) { s->push(right); right = right->next; } //比較鏈表左右兩邊節(jié)點是否相等 while (!s->empty()) { if (head->next->data != s->top()->data) return false; s->pop(); head = head->next; } return true;}希望本文所述對大家C++程序設計有所幫助。
新聞熱點
疑難解答
