🌏引言

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

🧭链表的回文结构

🚩🚩题目描述：

对于一个链表，请设计一个时间复杂度为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

🚩🚩思路解析：

回文字符串的中间节点两边的元素，如果从两头两中间进行比对的话，每一个里面的元素完全相同

🚩🚩🚩寻找中间节点

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

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

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;}
}

⭕总结

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