溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了C++判斷一個鏈表是否為回文結構的方法。分享給大家供大家參考，具體如下：
題目：
給定一個鏈表頭節點head，請判斷是否為回文結構
例如：
1->2->1 true
1->2->2->1 true
1->2->3->4->2->1 false
解題思路及代碼
1、找到鏈表中間節點，然后將鏈表中間節點的右邊所有節點放入一個棧中。
2、然后從鏈表首節點和棧頂元素一一對比，不相等則return false。
算法C++代碼：
鏈表節點結構定義
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;//保存中間節點的下一個節點(若為偶數則為偏右的中間節點)
pLinkedList cur = head; //快指針
while (cur->next != NULL && cur->next->next != NULL)
{
right = right->next;
cur = cur->next->next;
}
//當鏈表總結點個數為奇數情況時：
if (cur->next != NULL && cur->next->next == NULL)
right = right->next;
//將鏈表右邊的節點放入一個棧中
stack<pLinkedList>* s = new stack<pLinkedList>();
while (right != NULL)
{
s->push(right);
right = right->next;
}
//比較鏈表左右兩邊節點是否相等
while (!s->empty())
{
if (head->next->data != s->top()->data)
return false;
s->pop();
head = head->next;
}
return true;
}
希望本文所述對大家C++程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
