最近從極客時(shí)間上買(mǎi)了一份數(shù)據(jù)結(jié)構(gòu)與算法的課评汰，正在學(xué)習(xí)當(dāng)中纷捞。然后目前學(xué)到了鏈表這塊，有個(gè)課后思考是 ：用單鏈表實(shí)現(xiàn)回文串键俱。
評(píng)論底下 人才輩出兰绣，我看了一個(gè)網(wǎng)友的評(píng)論，使用快慢指針的方法來(lái)進(jìn)行實(shí)現(xiàn)算法编振。
https://github.com/andavid/leetcode-java/blob/master/note/234/README.md
我是從這個(gè)地方看到的代碼缀辩，然后自己仔細(xì)分析之后與大家共享。
話不多說(shuō)貼代碼：
根據(jù)快慢指針踪央， 判斷以下 fast 是否為null臀玄，如果是奇數(shù)，fast不為null畅蹂，slow 再遷移一位不用判斷最中間的數(shù)健无，prev和slow的值比較即可。 例: a->b->c->b->a->null , 到比較之前隊(duì)列變成null<-a<-b c->b->a->null 此時(shí)slow 是 c->b->a->null的b節(jié)點(diǎn)液斜，prev 為 null<-a<-b的b節(jié)點(diǎn)累贤，然后挨個(gè)對(duì)比即可叠穆。
如果是偶數(shù)，fast為null臼膏，slow不動(dòng)硼被，prev和slow的值比較即可。
例: a->b->c->c->b->a->null 到比較之前隊(duì)列變成null<-a<-b<-c c->b->a->null 此時(shí)slow 是 c->b->a->null的c節(jié)點(diǎn)渗磅，prev 為 null<-a<-b<-c的c節(jié)點(diǎn)嚷硫，然后挨個(gè)對(duì)比即可。
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode prev = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
ListNode next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
if (fast != null) {
slow = slow.next;
}
while (slow != null) {
if (slow.val != prev.val) {
return false;
}
slow = slow.next;
prev = prev.next;
}
return true;
}
}
加上我自己的分析應(yīng)該我覺(jué)得屏幕前的你可以看得懂了始鱼，看不懂也沒(méi)關(guān)系也可以自己拿筆或者自己實(shí)現(xiàn)一遍仔掸，就可以加深印象了。 共勉医清。
