前言
本系列主要講解鏈表的經典題
注：劃重點！！必考~
鏈表分割
牛客鏈接：鏈表的回文結構_牛客題霸_牛客網 (nowcoder.com)
- 題目描述：
對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的演算法，判斷其是否為回文結構，
給定一個鏈表的頭指標A，請回傳一個bool值，代表其是否為回文結構，保證鏈表長度小于等于900，
- 解題思路：
- 這里我們先找到中間結點（使用快慢指標法）
- 快指標每次走兩個結點的位置，慢指標每次走一個結點的位置
- 快指標走到結束位置時，慢指標恰到中間位置
- 從中間結點開始對接下來每個結點進行改變結點方向
- 最后對兩個頭結點開始逐個遍歷接下來的結點，直到相遇
- 圖示：
- 參考代碼：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
//快慢指標找到中間結點
struct ListNode*fast=A,*slow=A;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
struct ListNode*cur=slow;
//兩個指標用來逆轉節點方向
struct ListNode*prev=NULL,*next;
while(cur)
{
struct ListNode*Next=cur->next;
cur->next=prev;
prev=cur;
cur=Next;
}
//遍歷比較
struct ListNode*cur1=A,*cur2=prev;
while(cur1&&cur2)
{
if(cur1->val==cur2->val)
{
cur1=cur1->next;
cur2=cur2->next;
}
else
return false;
}
return true;
}
};- 結果：
每日k題無煩惱，點贊學習不得了~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/344239.html
標籤：其他
上一篇：Linux系統安裝與實驗基礎
下一篇：資料結構之佇列詳解