被问麻了。。。
大家好，我是吴师兄。
昨天有个同学私聊我，回文链表这道题目为什么不可以直接反转整个链表，然后一一比较？
先来看看他的代码：
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
if(head.next.next == null) return head.val == head.next.val;
ListNode dummy = reverseList(head);
while(dummy != null && head != null) {
if(dummy == head){
dummy = dummy.next;
head = head.next;
} else {
return false;
}
}
return true;
}
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode cur = reverseList(head.next);
head.next.next = head;
head.next = null;
return cur;
}
}
一眼看过去，很合理，逻辑很清晰：
1、先将链表进行反转，dummy 指向反转之后的链表头节点位置。
2、接下来从头到尾同时遍历 dummy 和 head 节点。
3、在遍历的过程中，如果发现两个节点不一样，那么就不是回文，否则继续判断接下来的节点是否相同。
但是，代码一提交，显示错误。
问题出在两个地方。
第一个问题是节点是否相同的比较。
原代码中是：
if(dummy == head){
....
}
这样比较的是两个节点的地址，除非指向同一个节点，否则始终是 false。
第二个问题比较隐蔽：在反转之后的链表中，head 指向的节点没有 next 节点，如下图所示。
也可以通过调试发现。
解决的方案是复制一个链表出来进行反转。
正确的代码如下：
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
if(head.next.next == null) return head.val == head.next.val;
ListNode dummy = reverseList(copyList(head));
while(dummy != null && head != null) {
if(dummy.val == head.val){
dummy = dummy.next;
head = head.next;
} else {
return false;
}
}
return true;
}
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode cur = reverseList(head.next);
head.next.next = head;
head.next = null;
return cur;
}
public ListNode copyList(ListNode head){
ListNode p = head;
ListNode list = null;
ListNode q = list;
while( p != null){
if( list == null){
list = new ListNode(p.val);
q = list;
}else{
ListNode n = new ListNode(p.val);
q.next = n;
q = q.next;
}
p = p.next;
}
return list;
}
}
所以说，整体上他的思路是没问题的，就是一些细节需要修改，改一下，虽然效率不咋的，但还是可以通过的。
当然，这道题目有个进阶的要求：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
那么上面的做法就行不通了，因为申请了额外的空间，达不到 O(1) 空间复杂度。
但是，很多时候在面对一道没有做过的算法题，肯定是无法第一时间就想到最优解，都是先从暴力解法入手，逐步优化。
算法训练是一个系统工程，需要循序渐进，太过于急功近利，没想出最优解就不写代码，很容易产生挫败感，带来反效果。
在这里给大家一个建议：如果你是初学者，不要去看那些代码写的很简短的题解。
就是那种不说人话的题解。
一来这种题解你看不懂，看了浪费时间；二来会让你产生焦虑感，为啥别人都这么牛逼。
反正没啥好处。
同时，也不要去追求最优解，先做到能白板写出一道题目的代码来，等到第二遍第三遍刷题的时候再想想怎么优化。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-01-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读