廣州 深圳 外貿(mào)網(wǎng)站建設(shè)搜索引擎在線
7.鏈表的回文結(jié)構(gòu)?
鏈表的回文結(jié)構(gòu)_牛客題霸_??途W(wǎng) (nowcoder.com)?
/*
解題思路:
此題可以先找到中間節(jié)點(diǎn),然后把后半部分逆置,最近前后兩部分一一比對,如果節(jié)點(diǎn)的值全部相同,則即為回文。
*/?
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {if (A == NULL || A->next == NULL)return true;ListNode* slow, *fast, *prev, *cur, *nxt;slow = fast = A;//找到中間節(jié)點(diǎn)while (fast && fast->next){slow = slow->next;fast = fast->next->next;}prev = NULL;//后半部分逆置cur = slow;while (cur){nxt = cur->next;cur->next = prev;prev = cur;cur = nxt;}//逐點(diǎn)比對while (A && prev){if (A->val != prev->val)return false;A = A->next;prev = prev->next;}return true;}
};
/*
此題也可以先把鏈表中的元素值全部保存到數(shù)組中,然后再判斷數(shù)組是否為回文。不建議使用這種解法,因?yàn)槿绻麤]有告訴鏈表最大長度,則不能同此解法
*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereint a[900] = {0};ListNode* cur = A;int n = 0;//保存鏈表元素while(cur){a[n++] = cur->val;cur = cur->next;}//判斷數(shù)組是否為回文結(jié)構(gòu)int begin = 0, end = n-1;while(begin < end){if(a[begin] != a[end])return false;++begin;--end;}return true;}
};
?