【数据结构】链表的回文结构-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】链表的回文结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🌏引言

单链表的操作算法是笔试面试中较为常见的题目。
本文将着重介绍平时面试中常见的关于链表的应用题目，马上要进行秋招了。希望对你们有帮助 ^_😀
【数据结构】链表的回文结构,数据结构,数据结构,链表,回文结构,java

🧭链表的回文结构

【数据结构】链表的回文结构,数据结构,数据结构,链表,回文结构,java

🚩🚩题目描述：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
         // write code here
    }
}

🚩🚩示例：

给定链表：11->22->33->22->11
返回值：true

🚩🚩思路解析：

回文字符串的中间节点两边的元素，如果从两头两中间进行比对的话，每一个里面的元素完全相同
【数据结构】链表的回文结构,数据结构,数据结构,链表,回文结构,java

🚩🚩🚩寻找中间节点

我们先寻找到中间节点，然后将中间节点后的链表部分进行局部偏转

寻找中间节点时用我们快慢指针的思想

fast：快指针，一次走两步
slow：慢指针，一次走一步
结束条件：
链表元素个数为偶数时：fast.next == null;
链表元素个数为奇数时：fast == null;

寻找中间节点代码如下

ListNode fast = A;
        ListNode slow = A;
        //找中间节点
        while(fast != null||fast.next != null) {
            //快指针，一次走两步
            fast = fast.next.next;
            //慢指针，一次走一步
            slow = slow.next;
        }

🚩🚩🚩局部翻转

接下来我们要对局部进行翻转

翻转单链表，我们首先设一个cur节点为我们当前所需要翻转的节点；还有一个curNext记录cur下一节点

翻转时：

先用curNext记录cur下一节点的位置
然后将cur.next置为slow，让cur节点指向slow
再将cur节点设为slow
最后让cur置为curNext，进行下一节点的翻转

结束条件：cur == null；

代码实现如下

  ListNode cur = slow.next;
        //局部翻转
        while( cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

🚩🚩🚩判断是否回文

接下来我们就要判断是否回文

判断思想：

A节点与slow节点同时向中间节点进行遍历
对比其中元素是否相等
不相等返回false，相等则继续遍历，直到结束

结束条件：

当链表中节点数为奇数时，这时候A与slow会相遇，指向同一位置
所以条件为A == slow；
当链表中节点为偶数时，这时候A与slow是不会相遇的
但是如果两边都遍历完,A的下一节点指向的肯定是slow
所以条件为A.next == slow;

代码实现如下：

//判断是否回文
        while(slow != A&& A.next != slow) {
            if(slow.val != A.val) {
                return false;
            }
            slow = slow.next;
            A = A.next;
        }
        return true;

🚩🚩完整代码与注意事项

🚩🚩🚩注意事项：

结束条件不是循环的条件，不要搞混，不然进不去循环😭
要注意对传进来的数据进行判断与筛选

🚩🚩🚩完整代码

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        
        ListNode fast = A;
        ListNode slow = A;
        //找中间节点
        while(fast != null&&fast.next != null) {
            //快指针，一次走两步
            fast = fast.next.next;
            //慢指针，一次走一步
            slow = slow.next;
        }
        ListNode cur = slow.next;
        //局部翻转
        while( cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //判断是否回文
        while(slow != A&& A.next != slow) {
            if(slow.val != A.val) {
                return false;
            }
            slow = slow.next;
            A = A.next;
        }
        return true;
    }
}