題目描述
請判斷一個鏈表是否為回文鏈表，
示例 1:
2/n輸出: false","classes":[]}" data-cke-widget-upcasted="1" data-cke-widget-keep-attr="0" data-widget="codeSnippet">輸入: 1->2
輸出: false
示例 2:
2->2->1/n輸出: true","classes":[]}" data-cke-widget-upcasted="1" data-cke-widget-keep-attr="0" data-widget="codeSnippet">輸入: 1->2->2->1
輸出: true
來源：力扣（LeetCode）鏈接：https://leetcode-cn.com/problems/palindrome-linked-list
解題思路
尋找回文串的核心思想是從中心向兩端擴展，
因為回文串可能是基數也可能是偶數，長度為奇數時只存在一個中心點，長度為偶數時存在兩個中心點，
判斷是否為回文串的思路比較簡單，不需要考慮奇偶情況，從兩端向中心逼近即可，
（因為回文串是對稱的，所以正著讀和倒著讀應該是一樣的，這一特點是解決回文串問題的關鍵）
判斷單鏈表是否為回文鏈表：
關鍵單鏈表無法倒著遍歷，無法使用雙指標技巧，最簡單的辦法是把鏈表反轉存入新的鏈表，比較兩者是否一致，
其實，借助二叉樹后序遍歷的思路，不需要顯示反轉鏈表也可以倒敘遍歷鏈表，
鏈表其實也是可以有前序和后序遍歷的
實際上就是把鏈表節點放入一個堆疊，然后再拿出來，這時候元素的順序是反的，
還有更好的思路：
先通過雙指標的快慢指標找到鏈表的中點；
ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 指標現在指向鏈表中點
如果fast沒指向null說明鏈表長度為奇數（slow還要再往前一步），否則為偶數；
if (fast != null)
slow = slow.next;
從slow開始反轉后邊的鏈表就可以開始比較回文了，
該方法總體時間復雜度為O（n），空間復雜度為O（1）
參考來源：https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/shou-ba-shou-shua-lian-biao-ti-mu-xun-lian-di-gui-si-wei/pan-duan-hui-wen-lian-biao
解題代碼
方法一：
//鏈表后序遍歷方法，通過遞回方式反轉鏈表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode l;
public boolean isPalindrome(ListNode head) {
l = head;
return compVal(head);
}
private boolean compVal(ListNode r) {
if(r == null) {
return true;
}
boolean result = compVal(r.next);
if(result && (r.val == l.val)) {
l = l.next;
return true;
}
return false;
}
}
方法二：更好的思路
//通過快慢指標方式
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
//快慢指標找到鏈表中點
ListNode s = head, f = head;
while(f != null && f.next != null) {
s = s.next;
f = f.next.next;
}
if(f != null) {
s = s.next;
}
//反轉后半段鏈表
ListNode p=head, q=reverse(s);
//比較兩段鏈表
while(q!=null) {
if(p.val != q.val) {
return false;
}
p = p.next;
q = q.next;
}
return true;
}
public ListNode reverse(ListNode h) {
ListNode p = null, c = h;
while(c != null) {
ListNode n = c.next;
c.next = p;
p = c;
c = n;
}
return p;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/257986.html
標籤：其他
上一篇：Java 方法