C++數據結構與算法之判斷一個鏈表是否為回文結構的方法
更新時間：2017年05月08日 11:49:32 作者：難免有錯_
這篇文章主要介紹了C++數據結構與算法之判斷一個鏈表是否為回文結構的方法,結合實例形式分析了回文結構并結合實例給出了C++判斷回文的操作技巧,需要的朋友可以參考下
本文實例講述了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é)點(若為偶數則為偏右的中間節(jié)點)
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;
//將鏈表右邊的節(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++程序設計有所幫助。
相關文章
堆是計算機科學中一類特殊的數據結構的統(tǒng)稱，通常是一個可以被看做一棵完全二叉樹的數組對象。而堆排序是利用堆這種數據結構所設計的一種排序算法。本文將詳細介紹堆的結構與接口，需要的可以參考一下2022-04-04
這篇文章主要介紹了最小生成樹算法C語言代碼實例，有需要的朋友可以參考一下2013-12-12
本章主要介紹C語言與C++的內存管理，以C++的內存分布作為引入，介紹C++不同于C語言的內存管理方式（new delete對比 malloc free)，感興趣的朋友來看看吧2022-09-09
鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。本文將用C語言實現單鏈表，需要的可以參考一下2022-06-06
這篇文章主要為大家詳細介紹了C語言編寫洗牌發(fā)牌程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
C++中sln,vcxproj,vcxproj.filters,lib,dll,exe的含義說明
這篇文章主要介紹了C++中sln,vcxproj,vcxproj.filters,lib,dll,exe的含義說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05
C++中的Beep 函數是一個發(fā)出嗡鳴聲的函數，本文將利用這個函數實現制作一個簡單的聲音系統(tǒng)。文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下2022-12-12
這篇文章主要介紹了C++實現LeetCode(78.子集合),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
內存泄漏是 C/C++ 應用程序中最微妙、最難以發(fā)現的 bug,存泄漏是由于之前分配的內存未能正確解除分配而導致的, 內存泄漏的檢測工具有很多,CRT庫,是Visual Studio 自帶的,所以我們可以開箱即用,所以下面我們就來一起學習一下如何使用CRT庫檢測內存泄漏2024-06-06
這篇文章主要介紹了C語言實現順序表基本操作匯總,對學習數據結構的朋友有一定的借鑒價值,需要的朋友可以參考下2014-07-07