題目
設(shè)計(jì)一種方式檢查一個鏈表是否為回文鏈表野芒。
樣例
1->2->1 就是一個回文鏈表扳剿。
分析
鏈表由于其特殊的結(jié)構(gòu)，沒法像數(shù)組那樣判斷回文掂恕，所以比較原始的方法，先找到鏈表的中間節(jié)點(diǎn)废膘，然后將后半部分反轉(zhuǎn)竹海，然后逐個比較即可。
鏈表中的算法丐黄，通常以尋找鏈表中間節(jié)點(diǎn)，反轉(zhuǎn)鏈表孔飒，合并兩個鏈表這些基本操作構(gòu)成灌闺，所以掌握這些基本操作很重要。
例如本題中尋找鏈表的中間節(jié)點(diǎn)的方法坏瞄，就是用兩個指針一快一慢桂对，一個走兩步，一個走一步鸠匀，快指針先走到底了蕉斜，這時(shí)候慢指針就指向中間節(jié)點(diǎn)。
代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
/**
* @param head a ListNode
* @return a boolean
*/
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode middle = findMiddle(head);
middle.next = reverse(middle.next);
ListNode p1 = head, p2 = middle.next;
while (p1 != null && p2 != null && p1.val == p2.val) {
p1 = p1.next;
p2 = p2.next;
}
return p2 == null;
}
private ListNode findMiddle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
}
