基于单链表的回文序列判断

本文首发于 LOGI'S BLOG，由作者转载。

问题

假如字符串使用单向链表存储，如何判断其是否为回文序列？

思路

S1. 定义快慢指针，快指针每次走两步，慢指针每次走一步同时将所经链表指针逆向，直到快指针走至表尾（next 为 null），此时慢指针刚好处于中点（对于元素个数为偶数的链表，处于下中点，即后半部分的首节点）。

S2. 同时遍历前后半段链表，如完全相同则为回文序列。

S3. 恢复被逆序的链表。

举例

奇数序列：ABCBA

A -> B -> C -> B -> A // 初态
A <- B <- C -> B- > A // S1 后
         slow

偶数序列：ABCCBA

A -> B -> C -> C -> B -> A // 初态
A <- B <- C <- C -> B -> A // S1 后
              slow

时空复杂度

S1 的时间复杂度为 O(n/2)，空间复杂度 O(1)。
S2 的时间复杂度为 O(n/2)，空间复杂度 O(1)。
S3 的时间复杂度为 O(n/2)，空间复杂度 O(1)。
最终总的时间复杂度就是 O(n)，空间复杂度 O(1)。

代码实现

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;
        }
        // 保存中点用于恢复
        Node mid = slow;
        Node midPre = prev;

        // 奇数序列，从中点之后开始比较
        if (fast != null) {
            slow = slow.next;
        }
        while (slow != null) {
            if (slow.data != prev.data) {
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }

        // 再次逆向 midPre.next，恢复链表
        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;
    }
}