给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路及方法
我最初想的是先反转链表，然后用双指针从头对比，但这样就犯了一个弱智的错误，因为链表在内存的地址一样，反转链表后就没有原先的链表了，从何比对？
看到题目进阶，要求O(1)的空间，想到犯的错误，于是我们可以在原链表上进行修改，反转链表的后半部分，然后双指针分别指向前半链表开头和后半链表开头，一一对比。
找到链表的分界处使用双指针法，快指针走两步，慢指针走一步；
如果链表长度为奇数，那么最后的慢指针指向链表的中点，如长度为9，指向的是第五个节点，将后半链表slow.next反转即可；
如果链表长度为偶数，那么最后的慢指针指向前半链表的结尾节点，如长度为10，指向的是第五个节点，将后半链表slow.next反转即可。寻找前半链表的结尾节点代码如下：
public ListNode halfFirst(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;
}
反转链表代码如下，具体是 206. 反转链表：
public ListNode reverse(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
// 反转
cur.next = pre;
// 移动指针
pre = cur;
cur = next;
}
return pre;
}
总代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
// 长度为1
if (head.next == null) return true;
// 后半链表结尾节点
ListNode half = halfFirst(head);
// 反转后半链表
ListNode halfStart = reverse(half.next);
ListNode pt1 = head;
ListNode pt2 = halfStart;
while (pt1 != null && pt2 != null) {
if (pt1.val != pt2.val) return false;
pt1 = pt1.next;
pt2 = pt2.next;
}
return true;
}
public ListNode halfFirst(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 reverse(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
// 反转
cur.next = pre;
// 移动指针
pre = cur;
cur = next;
}
return pre;
}
}
结果如下：
网友评论