博文中会简要介绍Leetcode P0234题目分析及解题思路。
“Palindrome Linked List”是中规中矩的题目。题目的难点并不在于判断链表是否是回文链，而是在于控制时间复杂度在O(n)且空间复杂度为O(1)。本篇博文不会详细讲解空间复杂度为O(1)的方法，但是需要强调的是这种方法其实是本文解法的一种衍生。
Given a singly linked list, determine if it is a palindrome.
这道题的基本思路很简单，为了对称地比较一个链表前后端结点的值，我们可以将原链表翻转得到新链表，然后将新链表和原链表中的所有对应的结点逐一按序比较即可。
这个思路的衍生则是可以只翻转原链表的一半，例如后一半的链表，然后将原来的前一半链表和翻转后的后一半链表按序依次比较即可，这样可以控制时间复杂度为O(1)。不过无论是原型还是衍生，两个解法的时间复杂度都是O(n)。
以下是Java的题解代码实现。
/**
* 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) {
ListNode reversed = this.reverse(head);
ListNode p1 = head, p2 = reversed;
while (p1 != null) {
if (p1.val != p2.val)
return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}
private ListNode reverse(ListNode head) {
ListNode headNew = null, curr = head;
while (curr != null) {
ListNode node = new ListNode(curr.val, headNew);
headNew = node;
curr = curr.next;
}
return headNew;
}
}
以下是C++的题解代码实现。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode *reversed = this->_Reverse(head);
ListNode *p1 = head, *p2 = reversed;
while (p1) {
if (p1->val != p2->val)
return false;
p1 = p1->next;
p2 = p2->next;
}
return true;
}
private:
ListNode* _Reverse(ListNode *head) {
ListNode *head_new = nullptr, *curr = head;
while (curr) {
ListNode *node = new ListNode(curr->val, head_new);
head_new = node;
curr = curr->next;
}
return head_new;
}
};