废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【链表的相关判断】，使用【链表】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。
判断链表中是否有环【EASY】
判断链表中是否有环
题干
解题思路
使用快慢双指针遍历链表，有环则一定会相遇
代码实现
给出代码实现基本档案
基本数据结构：链表
辅助数据结构：无
算法：迭代
技巧：双指针
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {// 1 当链表尾null直接返回falseif (head == null) {return false;}// 2 定义快慢指针，快指针每次走两步，慢指针每次走一步ListNode fast = head;ListNode slow = head;// 3 直到快指针到链表结尾如果快慢还没有相遇则无环while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;// 如果中途相遇，则有环，停止遍历，直接返回if (fast == slow) {return true;}}return false;}
}
复杂度分析
时间复杂度：遍历链表，时间复杂度为O（N）
空间复杂度：无额外空间使用，空间复杂度为O（1）
判断链表是否为回文链表【EASY】
判断链表是否是回文结构
题干
解题思路
这题是让判断链表是否是回文链表，所谓的回文链表就是以链表中间为中心点两边对称。我们常见的有判断一个字符串是否是回文字符串，这个比较简单，可以使用两个指针，一个最左边一个最右边，两个指针同时往中间靠，判断所指的字符是否相等。但这题判断的是链表，因为这里是单向链表，只能从前往后访问，不能从后往前访问，所以使用判断字符串的那种方式是行不通的。但我们可以通过找到链表的中间节点然后把链表后半部分反转，最后再用后半部分反转的链表和前半部分一个个比较即可
- 使用快慢指针找到链表的中点，如果是奇数个，则舍弃中心点
- 将链表后半部分反转
- 双指针分别在前半部分后半部分移动，如果遇到不相等的值则返回false
最终如果指针到达链尾且值都相同则返回true
代码实现
给出代码实现基本档案
基本数据结构：链表
辅助数据结构：无
算法：迭代
技巧：双指针
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;/** public class ListNode {* int val;* ListNode next = null;* public ListNode(int val) {* this.val = val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类 the head* @return bool布尔型*/public boolean isPail (ListNode head) {// 1 判断入参，如果是空链表，返回falseif (head == null) {return false;}// 2 定义快慢指针，快指针每次两步，到结尾时，慢指针刚好到中间ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}// 如果fast不为null，则链表长度为奇数，且slow位于中点，中点不用判断，所以slow应该向后移一位if (fast != null) {slow = slow.next;}// 3 反转后半段回文链表，并且slow指向后半部分头部、fast回到头部，两个链表继续向后slow = reverse(slow);fast = head;while (slow != null) {if (slow.val != fast.val) {return false;} else {fast = fast.next;slow = slow.next;}}return true;}private ListNode reverse(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode pNext = cur.next;cur.next = pre;pre = cur;cur = pNext;}return pre;}
}
复杂度分析
时间复杂度：遍历链表，时间复杂度为O（N）
空间复杂度：无额外空间使用，空间复杂度为O（1）
