本文首發(fā)于 LOGI'S BLOG经伙，由作者轉(zhuǎn)載拘荡。

問題

假如字符串使用單向鏈表存儲，如何判斷其是否為回文序列接剩？

思路

S1. 定義快慢指針办成，快指針每次走兩步，慢指針每次走一步同時將所經(jīng)鏈表指針逆向搂漠，直到快指針走至表尾（next 為 null），此時慢指針剛好處于中點（對于元素個數(shù)為偶數(shù)的鏈表某弦，處于下中點桐汤，即后半部分的首節(jié)點）而克。

S2. 同時遍歷前后半段鏈表，如完全相同則為回文序列怔毛。

S3. 恢復(fù)被逆序的鏈表员萍。

舉例

奇數(shù)序列：ABCBA

A -> B -> C -> B -> A // 初態(tài)
A <- B <- C -> B- > A // S1 后
         slow

偶數(shù)序列：ABCCBA

A -> B -> C -> C -> B -> A // 初態(tài)
A <- B <- C <- C -> B -> A // S1 后
              slow

時空復(fù)雜度

S1 的時間復(fù)雜度為 O(n/2)，空間復(fù)雜度 O(1)拣度。
S2 的時間復(fù)雜度為 O(n/2)碎绎，空間復(fù)雜度 O(1)。
S3 的時間復(fù)雜度為 O(n/2)抗果，空間復(fù)雜度 O(1)筋帖。
最終總的時間復(fù)雜度就是 O(n)，空間復(fù)雜度 O(1)冤馏。

代碼實現(xiàn)

package com.logi.algorithm;

/**
 * @author LOGI
 * @version 1.0
 * @date 2019/7/6 0:46
 */
public class PalindromeExamination {
    public static void main(String[] args) {
        PalindromeExamination.testSequence("ABCBA");
        PalindromeExamination.testSequence("ABCBB");
        PalindromeExamination.testSequence("ABCCBA");
        PalindromeExamination.testSequence("ABCCBB");
    }

    public static void testSequence(String sequence) {
        SinglyLinkedList list = new SinglyLinkedList(sequence);
        String determination = list.isPalindrome() ? "" : "not ";
        System.out.println(sequence + " is " + determination + "a palindrome.");
    }
}

class SinglyLinkedList {
    Node head;

    public SinglyLinkedList(String sequence) {
        for (int i = sequence.length() - 1; i >= 0; i--) {
            this.insert(sequence.charAt(i));
        }
    }

    public void insert(char elem) {
        Node newNode = new Node(elem);
        newNode.next = this.head;
        this.head = newNode;
    }

    public boolean isPalindrome() {
        if (this.head == null || this.head.next == null) {
            return false;
        }
        Node prev = null;
        Node next;
        Node slow = this.head;
        Node fast = this.head;

        // 判斷 fast.next 是否為 null日麸，在此之前也要保證 fast 不為 null
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            // 逆向 slow.next
            next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }
        // 保存中點用于恢復(fù)
        Node mid = slow;
        Node midPre = prev;

        // 奇數(shù)序列，從中點之后開始比較
        if (fast != null) {
            slow = slow.next;
        }
        while (slow != null) {
            if (slow.data != prev.data) {
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }

        // 再次逆向 midPre.next逮光，恢復(fù)鏈表
        while (midPre != null) {
            next = midPre.next;
            midPre.next = mid;
            mid = midPre;
            midPre = next;
        }
        return true;
    }
}

class Node {
    Node next;
    char data;

    public Node(char elem) {
        this.data = elem;
        this.next = null;
    }
}