脚撕LeetCode(面试02.06)Easy
题目地址：https://leetcode-cn.com/problems/palindrome-linked-list-lcci/
编写一个函数，检查输入的链表是否是回文的。
示例 1：
输入：1->2
输出：false
示例 2：
输入：1->2->2->1
输出：true进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
这道题的题意和9题类似，就是判断输入的链表是不是回文，既数组从中间切开两边是对称的。
一、爆破法
首先想到的就是最蠢的办法，先把链表挪动到数组里面，然后头尾遍历数组，出现异常马上返回false，执行完了就返回true。
这里犯了个小错误，忘了list里面放的是Integer，直接if的时候用了== ，导致[-129，-129]这个用例报错了
执行结果如下：
26 / 26 个通过测试用例
状态：通过
执行用时: 4 ms
内存消耗: 42.2 MB
public static boolean isPalindromeMe(ListNode head) {
if (null == head) return true;
List<Integer> list = new ArrayList<>();
ListNode item = head;
while (null != item) {
list.add(item.val);
item = item.next;
}
int headIndex = 0, endIndex = list.size() - 1;
while (headIndex < endIndex) {
if (!list.get(headIndex).equals(list.get(endIndex))) return false;
headIndex++;
endIndex--;
}
return true;
}当然结果是很不理想的，毕竟有进阶做法，我们看看大佬们的做法
在看官方方法之前要学习一下什么叫快慢指针
快慢指针就是定义两根指针，移动的速度一快一慢，以此来制造出自己想要的差值。这个差值可以让我们找到链表上相应的节点。
概念的意思就是，只需要根据我们的需求，去创造一快一慢的两个指针，这就是快慢指针
那么快慢指针快慢的进度没有什么特殊要求，如果你要的是链表的一半那么快针的步长就是慢针的2倍；如果你要链表的倒数第二个，那么快慢针的步长差距就是1；判断链表中有没有环只需要用快针是慢针的2倍看看会不会相遇即可。
二、官方快慢指针法
这道题的快慢针很明显就是快针是慢针的双倍。
他先用快慢针找到中间位置，然后再反转后半个链表，对比完了之后再还原链表。
这里的时间是2ms
而删除掉对比后再反转回来的步骤，时间直接变成1ms，超越了100%
执行结果如下：
26 / 26 个通过测试用例
状态：通过
执行用时: 2 ms
内存消耗: 41 MB
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}官方答案的思想是好的，用完给人家复原，避免后续使用出现的问题，但是刷leetcode大部分人是不讲武德的，解决完自己的事情就可以了，毕竟这是算法，不是工作。
今天学到了快慢针的用法，不算亏，毕竟以前天天听说快慢针，今天算是见识到了。
腾讯云开发者
