快捷導(dǎo)航

C++數(shù)據(jù)結(jié)構(gòu)與算法之判斷一個(gè)鏈表是否為回文結(jié)構(gòu)的方法

更新時(shí)間：2017年05月08日 11:49:32 作者：難免有錯(cuò)_

這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)與算法之判斷一個(gè)鏈表是否為回文結(jié)構(gòu)的方法,結(jié)合實(shí)例形式分析了回文結(jié)構(gòu)并結(jié)合實(shí)例給出了C++判斷回文的操作技巧,需要的朋友可以參考下

本文實(shí)例講述了C++判斷一個(gè)鏈表是否為回文結(jié)構(gòu)的方法。分享給大家供大家參考，具體如下：

題目：

給定一個(gè)鏈表頭節(jié)點(diǎn)head，請(qǐng)判斷是否為回文結(jié)構(gòu)

例如：

1->2->1 true
1->2->2->1 true
1->2->3->4->2->1 false

解題思路及代碼

1、找到鏈表中間節(jié)點(diǎn)，然后將鏈表中間節(jié)點(diǎn)的右邊所有節(jié)點(diǎn)放入一個(gè)棧中。

2、然后從鏈表首節(jié)點(diǎn)和棧頂元素一一對(duì)比，不相等則return false。

算法C++代碼：

鏈表節(jié)點(diǎn)結(jié)構(gòu)定義

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é)點(diǎn)的下一個(gè)節(jié)點(diǎn)(若為偶數(shù)則為偏右的中間節(jié)點(diǎn))
  pLinkedList cur = head;      //快指針
  while (cur->next != NULL && cur->next->next != NULL)
  {
    right = right->next;
    cur = cur->next->next;
  }
  //當(dāng)鏈表總結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)情況時(shí)：
  if (cur->next != NULL && cur->next->next == NULL)
    right = right->next;
  //將鏈表右邊的節(jié)點(diǎn)放入一個(gè)棧中
  stack<pLinkedList>* s = new stack<pLinkedList>();
  while (right != NULL)
  {
    s->push(right);
    right = right->next;
  }
  //比較鏈表左右兩邊節(jié)點(diǎn)是否相等
  while (!s->empty())
  {
    if (head->next->data != s->top()->data)
      return false;
    s->pop();
    head = head->next;
  }
  return true;
}

希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。

您可能感興趣的文章:

相關(guān)文章

C語言詳解如何實(shí)現(xiàn)堆及堆的結(jié)構(gòu)與接口
堆是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱，通常是一個(gè)可以被看做一棵完全二叉樹的數(shù)組對(duì)象。而堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。本文將詳細(xì)介紹堆的結(jié)構(gòu)與接口，需要的可以參考一下
2022-04-04
最小生成樹算法C語言代碼實(shí)例
這篇文章主要介紹了最小生成樹算法C語言代碼實(shí)例，有需要的朋友可以參考一下
2013-12-12
C++圖文并茂分析講解內(nèi)存管理
本章主要介紹C語言與C++的內(nèi)存管理，以C++的內(nèi)存分布作為引入，介紹C++不同于C語言的內(nèi)存管理方式（new delete對(duì)比 malloc free)，感興趣的朋友來看看吧
2022-09-09
C語言數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)現(xiàn)
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文將用C語言實(shí)現(xiàn)單鏈表，需要的可以參考一下
2022-06-06
C語言編寫洗牌發(fā)牌程序
這篇文章主要為大家詳細(xì)介紹了C語言編寫洗牌發(fā)牌程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-02-02
C++中sln,vcxproj,vcxproj.filters,lib,dll,exe的含義說明
這篇文章主要介紹了C++中sln,vcxproj,vcxproj.filters,lib,dll,exe的含義說明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2024-05-05
基于C++實(shí)現(xiàn)一個(gè)簡(jiǎn)單的音樂系統(tǒng)
C++中的Beep 函數(shù)是一個(gè)發(fā)出嗡鳴聲的函數(shù)，本文將利用這個(gè)函數(shù)實(shí)現(xiàn)制作一個(gè)簡(jiǎn)單的聲音系統(tǒng)。文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下
2022-12-12
C++實(shí)現(xiàn)LeetCode(78.子集合)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(78.子集合),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07
C++使用CRT庫檢測(cè)內(nèi)存泄漏的方法詳解
內(nèi)存泄漏是 C/C++ 應(yīng)用程序中最微妙、最難以發(fā)現(xiàn)的 bug,存泄漏是由于之前分配的內(nèi)存未能正確解除分配而導(dǎo)致的, 內(nèi)存泄漏的檢測(cè)工具有很多,CRT庫,是Visual Studio 自帶的,所以我們可以開箱即用,所以下面我們就來一起學(xué)習(xí)一下如何使用CRT庫檢測(cè)內(nèi)存泄漏
2024-06-06
C語言實(shí)現(xiàn)順序表基本操作匯總
這篇文章主要介紹了C語言實(shí)現(xiàn)順序表基本操作匯總,對(duì)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的朋友有一定的借鑒價(jià)值,需要的朋友可以參考下
2014-07-07