原题
请判断一个链表是否为回文链表。
示例1：
输入： 1->2
输出： false
示例2：
输入： 1->2->2->1
输出： true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解法
思想
双指针解法：
一个快指针一个慢指针，快指针每次移两步，慢指针每次移一步，这样快指针的落点有两种情况：
- 落在最后一个节点上，此时链表节点为奇数个，慢指针落在中间节点上。
- 落在最后一个节点指向的null上，此时链表节点为偶数个，慢指针落在中间靠右第一个节点上。
慢指针将链表分成了两半，将前半部分反转，再与后半部分比较，即可获取结果
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while(fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
pre.next = prepre;
prepre = pre;
}
//链表节点个数为奇数
if(fast != null) {
slow = slow.next;
}
while(pre != null && slow != null) {
if(pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode234-%e5%9b%9e%e6%96%87%e9%93%be%e8%a1%a8/
相关推荐
-
leetcode999-车的可用捕获量
原题 999. 车的可用捕获量 - 力扣（LeetCode） 解法 思想 这道题题目有点难理解，其实就是上下左右搜索，质量有点低了。 代码 class Solution { cha...
-
leetcode14-最长公共前缀
原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “...
-
leetcode485-最大连续1的个数
原题 给定一个二进制数组， 计算其中最大连续1的个数。 示例 1: 输入： [1,1,0,1,1,1] 输出： 3 解释： 开头的两位和最后的三位都是连续1，所以最大连续1的个数是...
-
剑指offer59-队列的最大值
原题（来源Leetcode） 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的时间复杂度...
-
蓝桥杯试题-哈夫曼树
原题 Description Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1}，用这列...
-
leetcode313-超级丑数
原题 编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 示例: 输入： n = 12, primes = [2...
-
leetcode636-函数的独占时间
原题 给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。 每个函数都有一个唯一的 Id，从 0 到 n-1，函数可能会递归调用或者被其他函数调用。 日志是具有以...
-
leetcode994-腐烂的橘子
原题 在给定的网格中，每个单元格可以有以下三个值之一： 值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜...
-
leetcode189-旋转数组
原题 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。 示例1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4...
-
leetcode99-恢复二叉搜索树
原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下，恢复这棵树。 示例 1: 输入: [1,3,null,null,2] 1 ...