寒光博客

[java] 回文链表检测
如何高效的检测单链表是否是回文链表呢 方法一 遍历一遍 计数 然后再找到中间node 开始对比 方法二 进...
扫描右侧二维码阅读全文
17
2019/10

[java] 回文链表检测

如何高效的检测单链表是否是回文链表呢

  • 方法一
    遍历一遍 计数 然后再找到中间node 开始对比

  • 方法二
    进步指针f、s后者是前者两倍 到null截至
    同时栈入f 判断s是否null 来决定和栈出对比的起点

代码

package _09_Linear.list;

import java.util.Stack;

/**
 * 回文链表 检测回文
 */
public class PalindromeLinkedList {
    static class Node {
        Object value;

        Node next;

        Node(Object value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 4, 3, 2, 1};
        int arr1[] = {1, 2, 3, 4, 5, 3, 2, 1};
        int arr2[] = {1, 2, 3, 4, 3, 2, 1};
        Node head = new Node(null);
        Node p = head;
        for (int i : arr) {
            p.next = new Node(i);
            p = p.next;
        }
        System.out.println(checkPalindrome(head));
    }

    private static boolean checkPalindrome(Node head) {
        Node f = head.next;
        Node s = head.next;
        Stack<Node> stack = new Stack<>();
        while (s != null && s.next != null) {
            stack.push(f);//入栈
            f = f.next;
            s = s.next.next;
        }
        if (s != null) {//奇数个//1 2 3 4(f) 1 2 3 4(s) s==null 就是  奇数个
            f = f.next;//后移
        }
        System.out.println("第二个指针的位置:" + f.value);
        while (!stack.empty()) {
            if (stack.pop().value == f.value) {//出栈
                f = f.next;
            } else {
                return false;
            }
        }
        return true;
    }

}
本文作者:Author:     文章标题:[java] 回文链表检测
本文地址:https://dxoca.cn/java/300.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:October 17th, 2019 at 09:36 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment