JAVA链表中的回文链表结构

全栈程序员站长

发布于 2022-08-23 20:26:16

8980

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

作为一个java初学者，最近遇到了回文链表结构这个难题，经过一番学习总算搞清楚个大概。

先来说一下什么是回文链表，会问链表在我们生活中经常能够遇到。会问链表的结构就是

例如：1->2->3->2->1。我们将它反转过来还是与原链表相同，这种就称为回文结构。

具体方法：1.先找到链表的中间位置

2.然后将中间位置的链表反转

3.从两边向中间遍历

代码如图

class Node {
    public int data;
    public Node next;
    //构造方法
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
public class MyLinkedList {
    public Node head;//保存单链表的头节点的引用
 public boolean chkPalindrome() {
        //判断头节点是否为空
        if(this.head == null) {
            return false;
        }
        //判断头节点的next是否为空，如果为空，证明只有一个链表，就是回文链表
        if(this.head.next == null) {
            return true;
        }
        //找出链表的中间位置
        Node fast = this.head;
        Node slow = this.head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //把中间位置之后的链表反转
        Node cur = slow.next;
        while(cur != null) {
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //从两边向中间遍历
        while(slow != this.head) {
            if(slow.data != this.head.data) {
                return false;
            }
            if(this.head.next == slow) {
                return true;
            }
            slow = slow.next;
            this.head = this.head.next;
        }
        return true;
    }
}

类似的链表题还有很多，我也是刚刚接触，这个博客就当复习了。如果有不对的地方还请大佬指正。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/139544.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年5月7，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法