思路 简单的方法是遍历一边链表，存入数组，再从首尾往中间判断是否相等。但是题目说了，进阶的解法是空间复杂度为O(1)，首先排除递归反转链表，倒是可以利用迭代来反转链表。在优化下，不用反转整条链表来比较，只需反转半条即可。 一次就AC了，爽 题目 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 …

思路 算是入门题了，运用双指针即可。 题目 给你一个字符串 s，找到 s 中最长的回文子串。   示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入：s = "cbbd" 输出："bb" 示例 3： 输入：s = "a" 输出："a" 示例 4： 输入：s = "ac" 输出："a…

思路 判断是否为回文字符串，最开始想到的是找到中点，利用双指针往外扩。后来发现直接从头尾往中间收就行了。 有两个注意点 本题有只判断字符和数字，其他的符号不管 大小写不敏感 在leetcode评论区学到个技巧 题目 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。  …

思路 反转链表II_92的进阶，主要是利用递归思想，拆解重复问题。 题目 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 进阶： 你可以设计一个只使用常数额外空间的…

思路 这种题就很烦，你说它难吧，它就是在反转链表_206的基础上增加了个数量限制。你说它不难吧，边界问题折磨死你。提交几次，调试半天才AC。 题目 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后…

思路 这题的解法有些独特，可能是我太久没接触几何相关的问题了，要是放在初中，应该还是能想出来。 两个链表都需要遍历，很容易想到双指针。先考虑简单情况，假如两个链表长度相等。双指针同时往前走，每走一步判断下是否相等。 假如链表长度不等，双指针同时往前走就不行了，即使调整速度也不好使。我们的目的是判断两个指针是否相等，链表相交部分长度是相等的，如果末端…

思路 基础的递归思维，再一次用到了虚拟头结点。 题目 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 示例 2： 输入：head = [1,2] 输出：[2,1] 示例 3： 输入：head = [] 输出：[] 提示： 链表中节点的数目范围是…

思路 利用快慢指针，快指针先走n步，慢指针才开始走，快指针走到终点时，慢指针所在的位置就是倒数n节点。 题目 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 进阶：你能尝试使用一趟扫描实现吗？   示例 1： 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2： 输入：head = [1…

思路 环形链表_141的升级版，根据上一题已经能求出快慢指针在C点相遇，接下来就是求B点。 假设环形周长为m 慢指针路程*2=快指针路程 2(AB+BC)=AB+m*n+BC 2AB+2BC=AB+m*n+BC AB+BC=m*n AB=CB+m*n m和n的值不用管，重点是一个指针从A走到B，另一个指针从C出发，走到了B。而上一题遍历结束时，快慢…

思路 龟兔赛跑的套路，使用快慢指针，相遇即有环。 注意：是慢指针正常速度，快指针两倍速度。不是快指针正常速度，慢指针1/2速度。不然会超时 题目 给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 …