IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 不考虑空间复杂度和考虑空间复杂度的情况下判断一个单向链表是否是回文的 -> 正文阅读

[数据结构与算法]不考虑空间复杂度和考虑空间复杂度的情况下判断一个单向链表是否是回文的

准备工作:

class Node {
    public int value;
    public Node next;

    public Node(int value) {
        this.value = value;
    }
}
//创建一个单链表类方便管理单链表
class NodeList {
    public Node first;
    //统计单链表中元素个数
    public int count = 1;
    //此处只给了一个含参构造方法,要求创建一个单链表的时候给出头
    public NodeList(Node first) {
        this.first = first;
    }
    public void add(Node node) {
        Node tmp = first;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        count++;
        tmp.next = node;
    }
}

搞个链表:

public class Test {
    public static void main(String[] args) {
        //创建单链表并且添加元素
        NodeList nodeList = new NodeList(new Node(1));
        nodeList.add(new Node(2));
        nodeList.add(new Node(3));
        nodeList.add(new Node(2));
        nodeList.add(new Node(1));
        //判断是否回文
        System.out.println(isPlalindrome不考虑(nodeList));
        System.out.println(isPlalindrome考虑(nodeList));
    }

}

正式操作

一:在不考虑空间复杂度的情况下

将其压入栈中,根据栈后入先出的特点完成判断

?

/**
     * 在不考虑空间复杂度的时候
     * 将链表中元素依次加入栈中
     * 然后从栈中后半截依次弹出,将其与链表中的元素依次比较
     */
    public static boolean isPlalindrome不考虑(NodeList nodeList) {
        Stack<Node> stack = new Stack<>();
        Node tmp = nodeList.first;
        while (tmp != null) {
            stack.push(tmp);
            tmp = tmp.next;
        }
        Node tmp1 = nodeList.first;
        int i = stack.size()/2;
        while (i != 0) {
            if (stack.pop().value != tmp1.value) {
                return false;
            }
            tmp1 = tmp1.next;
            i--;
        }
        return true;
    }

二:在空间复杂度尽可能低的情况下

public static boolean isPlalindrome考虑(NodeList nodeList) {
        if (nodeList.count == 1) {
            return true;
        }
        if (nodeList.count == 2) {
            if (nodeList.first.value == nodeList.first.next.value) {
                return true;
            } else {
                return false;
            }
        }

        Node p1 = nodeList.first;
        Node p2 = nodeList.first;
        Node tmp = null;

        //如果是偶数个
        if (nodeList.count % 2 == 0) {
            //使得p1在最后指向前半截最后一个,p2指向最后一个
            p2 = p2.next;
            while (p2.next != null) {
                p2 = p2.next.next;
                p1 = p1.next;
            }
            p2 = p1;
            while (p1.next == null) {
                tmp = p1.next.next;
                p1.next = p1;
                p1 = tmp;
            }
        }
        //如果是奇数个
        if (nodeList.count % 2 == 1) {
            //使p1指向中间,p2指向最后一个
            while (p2.next != null) {
                p2 = p2.next.next;
                p1 = p1.next;
            }
        }

        reverse(p1);
        //将p1指向最开始
        p1 = nodeList.first;
        while (p2.next != null) {
            if (p2.value != p1.value) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    //传入单链表中的一个节点,使得该节点后所有的节点反向指向,而该节点指向null,
    public static void reverse(Node nodeFirst) {
        if (nodeFirst == null || nodeFirst.next == null) {
            return;
        }
        Node p1 = nodeFirst;
        Node p2 = nodeFirst.next;
        nodeFirst.next = null;
        Node tmp = null;
        while (p2 != null) {
            tmp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = tmp;
        }
    }

如果觉得文章对你有用,别忘了点赞哦~

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-03-13 22:03:13  更:2022-03-13 22:07:07 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 13:46:31-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码