🌏引言
单链表的操作算法是笔试面试中较为常见的题目。
本文将着重介绍平时面试中常见的关于链表的应用题目，马上要进行秋招了。希望对你们有帮助 _😀
🧭链表的回文结构
🚩🚩题目描述：
对于一个链表，请设计一个时间复杂度为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; } }
⭕总结
关于《【数据结构】链表的回文结构》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！
