LeetCode—回文链表(快慢指针+反转链表)
程序员文章站
2022-06-18 10:54:13
...
回文链表(简单)
2020年6月4日
题目来源:力扣
解题
第一思路是用数组来记录链表的值,双指针从两端开始对比数值,如果不同就返回false,到最后相同就返回true。
但题目要求O(n)的时间复杂度,O(1)的空间复杂度,那就不能额外开辟空间了。
本题解做法
- 拿到链表的中心点,把链表分成前后两部分
- 把后段链表的顺序反转过来
- 前后两段链表按顺序对比数值
- 为了不破坏原先的链表,对比完不论结果,都要把后段链表反转回来
- 返回对比结果
具体做法
链表不能直接获取长度,我们需要确定回文链表的中心点,这时候可以用快慢指针来找中心点(快慢指针真的太香了)
先来看奇数的情况,快指针到末尾时,慢指针可以找到3这个中心节点
偶数的情况,快指针走了一步就停下来了,现在慢指针指向2这个节点,虽然不是中心节点,但2后面一个节点就是链表的第二部分了
我们可以看出,不管链表节点个数是奇数还是偶数,我们都能找到两段链表的中心断点
接下来要反转链表,反转链表的做法可以参考我这篇文章的思路反转链表
接着我们就按照顺序来对比两段链表的数值了,由于奇数偶数的不确定性,这里采用后段链表来作为结束标志。
最后,恢复原链表,返回结果。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null) return true;
//快慢指针法,找出中心点
ListNode center=fastandslow(head);
//设置第二段链表的开头并反转链表
ListNode secondstart=reverseList(center.next);
ListNode firststart=head;
boolean result=true;
while(result && secondstart!=null){
if(firststart.val!=secondstart.val) result=false;
firststart=firststart.next;
secondstart=secondstart.next;
}
center.next=reverseList(secondstart);
return result;
}
public ListNode fastandslow(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;
}
public ListNode reverseList(ListNode start){
ListNode pre=null;
ListNode cur=start;
while(cur!=null){
ListNode tmp=cur.next;
cur.next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
}