您好,登錄后才能下訂單哦!
這篇文章主要講解了“C++的回文鏈表是什么”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來(lái)研究和學(xué)習(xí)“C++的回文鏈表是什么”吧!
請(qǐng)判斷一個(gè)鏈表是否為回文鏈表。
思路
總結(jié)
示例 1:
輸入: 1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
1.用快慢指針,快指針有兩步,慢指針走一步,快指針遇到終止位置時(shí),慢指針就在鏈表中間位置
2.同時(shí)用pre記錄慢指針指向節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn),用來(lái)分割鏈表
3.將鏈表分為前后均等兩部分,如果鏈表長(zhǎng)度是奇數(shù),那么后半部分多一個(gè)節(jié)點(diǎn)
4.將后半部分反轉(zhuǎn) ,得cur2,前半部分為cur1
5.按照cur1的長(zhǎng)度,一次比較cur1和cur2的節(jié)點(diǎn)數(shù)值
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { if(head==nullptr||head->next==nullptr) return true; ListNode* fast=head; //快指針 ListNode* slow=head; //慢指針,找到鏈表的中間位置 ListNode* pre=head; //慢指針的前一個(gè)指針,用來(lái)分割鏈表 while(fast&&fast->next){ //循環(huán)條件是fast和fast的下一個(gè)節(jié)點(diǎn)是否都存在,不用寫fast!=nullptr&&fast->next!=nullptr,直接fast&&fast->next pre=slow; fast=fast->next->next; slow=slow->next; //per=slow; //這句不能放在這,這里的slow是slow->next。只能放在slow=slow->next的前面。 } pre->next=nullptr; //分割鏈表。per是前半部分鏈表的最后一個(gè)節(jié)點(diǎn),所以是per的下一個(gè)結(jié)點(diǎn)為空,不是per==nullptr ListNode* cur1=head; //前半部分的鏈表 ListNode* cur2=reverse(slow); //對(duì)后半部分的鏈表進(jìn)行反轉(zhuǎn),reverse(ListNode* slow)錯(cuò)誤,調(diào)用不用寫類型ListNode* while(cur1){ //循環(huán)條件是cur是否為空 if(cur1->val!=cur2->val) // 若有一個(gè)不相等則返回false return false; cur1=cur1->next; // 判斷下一個(gè)節(jié)點(diǎn) cur2=cur2->next; // } return true; //都等于則true } //反轉(zhuǎn)鏈表 ListNode* reverse(ListNode* head){ ListNode* temp; //保存cur的下一個(gè)節(jié)點(diǎn),下一次要操作cur->next的節(jié)點(diǎn) ListNode* cur=head; ListNode* pre=nullptr; while(cur){ temp=cur->next; cur->next=pre; pre=cur; cur=temp; } return pre; } };
感謝各位的閱讀,以上就是“C++的回文鏈表是什么”的內(nèi)容了,經(jīng)過(guò)本文的學(xué)習(xí)后,相信大家對(duì)C++的回文鏈表是什么這一問(wèn)題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。