前言

学习了极客时间王铮老师的《数据结构与算法之美》中《06 | 链表(上):如何实现LRU缓存淘汰算法?》,课后思考留了一道算法题,
给定一个字符串,判断是否是回文字符串,而且呢,这个字符串不是普通的字符串,字符串中各个字符是以单向链表的数据结构首尾相连,看起来像下面这样:1 -> 2 -> 3 -> 0 -> 3 -> 2 -> 1,我们来一起看下这个算法可以如何实现。

算法

算法简述

这里介绍一种快慢指针的方法(所谓快慢指针,说白了就是两个变量而已)。
开始时,快慢指针都指向头结点,然后从头结点开始,,快指针每次走两步,慢指针每次走一步。
对于一个长度为奇数的链表,当快指针走到尾结点时,慢指针刚好走到这个链表最中间的那个节点。从头结点开始,慢指针走过的节点 next 引用都反转方向,指向之前指向自己的那个节点。然后从中间向两侧开始逐节点对比,一直对比到头尾节点,如果每次对比,内容都相同,则说明是一个回文字符串。

算法可视化

上面大致理清了思路,为了将思路更清晰,在撸代码之前让更多小伙伴理解,我用图片来说明一下。
我们还是基于长度为奇数的单向链表,因为长度为偶数的单向链表相对容易一些。

  • 首先,我们定义3个元素,用 fast 表示快指针,slow 表示慢指针,以及一个 pre 表示 slow 的上一个元素 fast尾结点方向走两步,然后将 slownext 指针指向上一个元素 pre,由于 slow 的上一个元素即 pre 初始状态是空,所以从图上看的效果,就是直接将 slownext 丢弃了。随后将 slow 赋给 preslow 向前走一步。大家注意这里,在将 slow 的指针指向pre前,我们需要一个局部变量 slowNext,来保存此时的 slow 最初的下一个元素,否则我们后续无法再获取到 slow 最初的下一个元素。
    loop1

  • 上面我们走了一个完整的快慢指针从头结点尾结点方向移动的逻辑,下面我放一个快指针从头结点一直走到尾结点完整过程。
    fast-arrived-at-end

  • 对于长度为奇数的单向链表,当 fast 走到尾结点时,slow 指向链表正中央的节点,判断 fast 的 下一个元素 next 为空时,表示 fast 走到尾结点,将 slow 继续向前走一步
    slow-to-right-side

  • 此时 slow 与 pre 的位置呈轴对称,且 pre 所处链表方向(向左) 与 slow 所处链表方向(向右)相反,若 pre 和 slow 分别向各自尾结点逐步前进,每前进一步,对比一次两个节点内容是否相同即可知道是否是回文字符串。
    pre-slow-go-self-end

  • pre 或者 slownext 指向的元素是否为空,来判断是否回文判断是否结束,并最终得到该字符串是否是回文字符串。
    the-end

代码实现

这里,我没加注释,上面已经图文讲解的很详细了。

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("1", d);
        Node b1 = new Node("2", c1);
        Node a1 = new Node("3", 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 + "}";
        }
    }
}

相关阅读

负载均衡算法之一致性 Hash 算法实现
负载均衡算法之加权轮询算法实现

About Me
后端开发工程师
GitHub Repos