原文鏈接：http://xueliang.org/article/detail/20200727003018759

前言

學習了極客時間王錚老師的《資料結構與演算法之美》中《06 | 鏈表（上）：如何實作LRU快取淘汰演算法?》，課后思考留了一道演算法題，
給定一個字串，判斷是否是回文字串，而且呢，這個字串不是普通的字串，字串中各個字符是以單向鏈表的資料結構首尾相連，看起來像下面這樣：1 -> 2 -> 3 -> 0 -> 3 -> 2 -> 1，我們來一起看下這個演算法可以如何實作，

演算法

演算法簡述

這里介紹一種快慢指標的方法（所謂快慢指標，說白了就是兩個變數而已），
開始時，快慢指標都指向頭結點，然后從頭結點開始，，快指標每次走兩步，慢指標每次走一步，
對于一個長度為奇數的鏈表，當快指標走到尾結點時，慢指標剛好走到這個鏈表最中間的那個節點，從頭結點開始，慢指標走過的節點 next 參考都反轉方向，指向之前指向自己的那個節點，然后從中間向兩側開始逐節點對比，一直對比到頭尾節點，如果每次對比，內容都相同，則說明是一個回文字串，

演算法可視化

上面大致理清了思路，為了將思路更清晰，在擼代碼之前讓更多小伙伴理解，我用圖片來說明一下，
我們還是基于長度為奇數的單向鏈表，因為長度為偶數的單向鏈表相對容易一些，

首先，我們定義3個元素，用 fast 表示快指標，slow 表示慢指標，以及一個 pre 表示 slow 的上一個元素 fast 向尾結點方向走兩步，然后將 slow 的 next 指標指向上一個元素 pre，由于 slow 的上一個元素即 pre 初始狀態是空，所以從圖上看的效果，就是直接將 slow 的 next 丟棄了，隨后將 slow 賦給 pre，slow 向前走一步，大家注意這里，在將 slow 的指標指向pre前，我們需要一個區域變數 slowNext，來保存此時的 slow 最初的下一個元素，否則我們后續無法再獲取到 slow 最初的下一個元素，
上面我們走了一個完整的快慢指標從頭結點往尾結點方向移動的邏輯，下面我放一個快指標從頭結點一直走到尾結點完整程序，
對于長度為奇數的單向鏈表，當 fast 走到尾結點時，slow 指向鏈表正中央的節點，判斷 fast 的下一個元素 next 為空時，表示 fast 走到尾結點，將 slow 繼續向前走一步
此時 slow 與 pre 的位置呈軸對稱，且 pre 所處鏈表方向（向左）與 slow 所處鏈表方向（向右）相反，若 pre 和 slow 分別向各自尾結點逐步前進，每前進一步，對比一次兩個節點內容是否相同即可知道是否是回文字串，
以 pre 或者 slow 的 next 指向的元素是否為空，來判斷是否回文判斷是否結束，并最終得到該字串是否是回文字串，

代碼實作

這里，我沒加注釋，上面已經圖文講解的很詳細了，

package org.xueliang.algorithm.linkedlist;

/**
 * @author xueliang
 * @since 2020-07-25 00:01
 */
public class Palindrome {

    public static void main(String[] args) {
        Node a = new Node("1", null);
        Node b = new Node("2", a);
        Node c = new Node("3", b);
        Node d = new Node("0", c);
        Node c1 = new Node("3", d);
        Node b1 = new Node("2", c1);
        Node a1 = new Node("1", b1);

        Node fast = a1;
        Node slow = a1;
        Node pre = null;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            Node slowNext = slow.next;
            slow.next = pre;
            pre = slow;
            slow = slowNext;
        }
        if (fast != null) {
            slow = slow.next;
        }
        boolean isPalindrome = true;
        while (pre != null) {
            if (!pre.text.equals(slow.text)) {
                isPalindrome = false;
                break;
            }
            pre = pre.next;
            slow = slow.next;
        }

        System.out.println("是否是回文字串：" + isPalindrome);
    }

    static class Node {

        Node(String text, Node next) {
            this.text = text;
            this.next = next;
        }

        private String text;

        private Node next;

        @Override
        public String toString() {
            return "Node{id:" + Integer.toHexString(hashCode()) + ",text:" + text + "}";
        }
    }
}

資料結構-基于單向鏈表的回文字串判斷

前言

演算法

演算法簡述

演算法可視化

代碼實作

相關閱讀