??引言
單鏈表的操作算法是筆試面試中較為常見的題目。
本文將著重介紹平時(shí)面試中常見的關(guān)于鏈表的應(yīng)用題目，馬上要進(jìn)行秋招了。希望對(duì)你們有幫助 _??
??鏈表的回文結(jié)構(gòu)
????題目描述：
對(duì)于一個(gè)鏈表，請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n),額外空間復(fù)雜度為O(1)的算法，判斷其是否為回文結(jié)構(gòu)。
給定一個(gè)鏈表的頭指針A，請(qǐng)返回一個(gè)bool值，代表其是否為回文結(jié)構(gòu)。保證鏈表長(zhǎng)度小于等于900。
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
}
}
????示例：
給定鏈表：11->22->33->22->11
返回值：true
????思路解析：
回文字符串的中間節(jié)點(diǎn)兩邊的元素，如果從兩頭兩中間進(jìn)行比對(duì)的話，每一個(gè)里面的元素完全相同
??????尋找中間節(jié)點(diǎn)
我們先尋找到中間節(jié)點(diǎn)，然后將中間節(jié)點(diǎn)后的鏈表部分進(jìn)行局部偏轉(zhuǎn)
尋找中間節(jié)點(diǎn)時(shí)用我們快慢指針的思想
fast：快指針，一次走兩步
slow：慢指針，一次走一步
結(jié)束條件：
鏈表元素個(gè)數(shù)為偶數(shù)時(shí)：fast.next == null;
鏈表元素個(gè)數(shù)為奇數(shù)時(shí)：fast == null;
尋找中間節(jié)點(diǎn)代碼如下
ListNode fast = A;
ListNode slow = A;
//找中間節(jié)點(diǎn)
while(fast != null||fast.next != null) {
//快指針，一次走兩步
fast = fast.next.next;
//慢指針，一次走一步
slow = slow.next;
}
??????局部翻轉(zhuǎn)
接下來我們要對(duì)局部進(jìn)行翻轉(zhuǎn)
翻轉(zhuǎn)單鏈表，我們首先設(shè)一個(gè)cur節(jié)點(diǎn)為我們當(dāng)前所需要翻轉(zhuǎn)的節(jié)點(diǎn)；還有一個(gè)curNext記錄cur下一節(jié)點(diǎn)
翻轉(zhuǎn)時(shí)：
- 先用curNext記錄cur下一節(jié)點(diǎn)的位置
- 然后將cur.next置為slow，讓cur節(jié)點(diǎn)指向slow
- 再將cur節(jié)點(diǎn)設(shè)為slow
- 最后讓cur置為curNext，進(jìn)行下一節(jié)點(diǎn)的翻轉(zhuǎn)
結(jié)束條件：cur == null；
代碼實(shí)現(xiàn)如下
ListNode cur = slow.next;
//局部翻轉(zhuǎn)
while( cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
??????判斷是否回文
接下來我們就要判斷是否回文
判斷思想：
- A節(jié)點(diǎn)與slow節(jié)點(diǎn)同時(shí)向中間節(jié)點(diǎn)進(jìn)行遍歷
- 對(duì)比其中元素是否相等
- 不相等返回false，相等則繼續(xù)遍歷，直到結(jié)束
結(jié)束條件：
- 當(dāng)鏈表中節(jié)點(diǎn)數(shù)為奇數(shù)時(shí)，這時(shí)候A與slow會(huì)相遇，指向同一位置
- 所以條件為A == slow；
- 當(dāng)鏈表中節(jié)點(diǎn)為偶數(shù)時(shí)，這時(shí)候A與slow是不會(huì)相遇的
- 但是如果兩邊都遍歷完,A的下一節(jié)點(diǎn)指向的肯定是slow
- 所以條件為A.next == slow;
代碼實(shí)現(xiàn)如下：文章來源：http://www.zghlxwxcb.cn/news/detail-661961.html
//判斷是否回文
while(slow != A&& A.next != slow) {
if(slow.val != A.val) {
return false;
}
slow = slow.next;
A = A.next;
}
return true;
????完整代碼與注意事項(xiàng)
??????注意事項(xiàng)：
- 結(jié)束條件不是循環(huán)的條件，不要搞混，不然進(jìn)不去循環(huán)??
- 要注意對(duì)傳進(jìn)來的數(shù)據(jù)進(jìn)行判斷與篩選
??????完整代碼
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
ListNode fast = A;
ListNode slow = A;
//找中間節(jié)點(diǎn)
while(fast != null&&fast.next != null) {
//快指針，一次走兩步
fast = fast.next.next;
//慢指針，一次走一步
slow = slow.next;
}
ListNode cur = slow.next;
//局部翻轉(zhuǎn)
while( cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//判斷是否回文
while(slow != A&& A.next != slow) {
if(slow.val != A.val) {
return false;
}
slow = slow.next;
A = A.next;
}
return true;
}
}
?總結(jié)
關(guān)于《【數(shù)據(jù)結(jié)構(gòu)】鏈表的回文結(jié)構(gòu)》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評(píng)指正，如果文章對(duì)您有幫助或者覺得作者寫的還不錯(cuò)可以點(diǎn)一下關(guān)注，點(diǎn)贊，收藏支持一下！文章來源地址http://www.zghlxwxcb.cn/news/detail-661961.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】鏈表的回文結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
