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

ゝ一纸荒年。 2024-04-17 10:43 63阅读 0赞

#### 文章目录 ####

*  ?引言
 *  ?\[链表的回文结构\](https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking)
 *   *  ??题目描述：
     *  ??示例：
     *  ??思路解析：
     *   *  ???寻找中间节点
         *  ???局部翻转
         *  ???判断是否回文
     *  ??完整代码与注意事项
     *   *  ???注意事项：
         *  ???完整代码
 *  ⭕总结

## ?引言 ##

单链表的操作算法是笔试面试中较为常见的题目。  
本文将着重介绍平时面试中常见的关于链表的应用题目，马上要进行秋招了。希望对你们有帮助 \_?  
![在这里插入图片描述][94b094fa0d0f42bcac0a437a41e1eff4.png]

## ?[链表的回文结构][Link 1] ##

![在这里插入图片描述][50b4622970384c5194dc327ef353d473.png]

### ??题目描述： ###

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

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

### ??示例： ###

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

### ??思路解析： ###

回文字符串的中间节点两边的元素，如果从两头两中间进行比对的话，每一个里面的元素完全相同  
![在这里插入图片描述][a7f45517219b43faa1f7fb7d07a7d61f.png]

#### ???寻找中间节点 ####

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

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

> fast：快指针，一次走两步  
> slow：慢指针，一次走一步  
> 结束条件：  
> 链表元素个数为偶数时：fast.next == null;  
> 链表元素个数为奇数时：fast == null;  
> ![在这里插入图片描述][6d6a091ef7cd4499bbeaf4f48a66e67f.png]

寻找中间节点代码如下

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，进行下一节点的翻转  
    ![在这里插入图片描述][d378e68aa6b3496fa25251dcbc0bc3fb.png]  
    结束条件：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；
 *  ![在这里插入图片描述][cbaa24e1c3cd42b6a971b665ffe2074a.png]
 *  当链表中节点为偶数时，这时候A与slow是不会相遇的
 *  但是如果两边都遍历完,A的下一节点指向的肯定是slow
 *  所以条件为A.next == slow;
 *  ![在这里插入图片描述][0d6b33feac4e411aaeda8ab21578ed1b.png]

代码实现如下：

//判断是否回文
            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;
        }
    }

## ⭕总结 ##

关于《【数据结构】链表的回文结构》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[94b094fa0d0f42bcac0a437a41e1eff4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/1fc9dafc2a3d4cce913cf4a4163b29bc.png
[Link 1]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[50b4622970384c5194dc327ef353d473.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/7092094acd2549faa2d623f5f085c373.png
[a7f45517219b43faa1f7fb7d07a7d61f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/ad8fbe5c147a41c59ab403e40d5c504c.png
[6d6a091ef7cd4499bbeaf4f48a66e67f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/f7c0a3db8c1c4a489d557e8bf3342c2f.png
[d378e68aa6b3496fa25251dcbc0bc3fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/408976a5968d4d818e92e83724b2f4b1.png
[cbaa24e1c3cd42b6a971b665ffe2074a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/1b0687908b594ace9a7e5bfe7b28c41a.png
[0d6b33feac4e411aaeda8ab21578ed1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/927613ae0b4344e197daa401994805f7.png