234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space? 234. Palindrome Linked List

---

本题要判断一个单向链表是否为回文链表。之前LeetCode Valid Palindrome判断的是数组，可以直接访问数组的头尾元素，但是链表不可以随机访问。 仔细观察一下，下面两条回文链表：

1. 1->2->3->4->5->4->3->2->1
2. 1->2->3->4->4->3->2->1

判断回文链表最原始的方法是从左往右读一遍和从右往左读一遍，如果读得的结果一样就是回文，比如第1条回文，从左往右是123454321，从右往左也是123454321，所以它是回文。 但是其实我们可以不用完整读一遍，我们只读一半就可以了，比如回文1的前半部分是1234，后半部分是4321，前半部分顺着读和后半部分倒着读都是1234，这样就足以说明是回文串了。 紧接着，对于链表，我们就有这样一种解题思路：首先找到链表的中间节点，然后把后半部分链表逆序，最后看看逆序的后半部分和顺序的前半部分是否相同。 找链表的中间节点的常规思路就是快慢指针，这个在很多题中都用到了，需要指出的是，回文链表有两种情况，一种是形如1的奇数个元素，另一种是形如2的偶数个元素。如果用快慢指针找中点，1能找到真正的中点5，2能找到前一个中点4，所以我们判断回文的时候，只需要把中点后面的链表逆序，然后只比较后半部分的链表元素。比如1的情况，逆序后半部分之后得到1->2->3->4，那么前半部分也只需要比较1->2->3->4，不需要比较5，因为这是奇数链表的中点，前后链表共享的元素；2的情况，逆序后半部分之后得到1->2->3->4，前半部分也是1->2->3->4，偶数长度的情况就会把中间的两个元素分到前后两部分。 完整代码如下：

class Solution {
public:
    bool isPalindrome(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return true;
        ListNode *faster = head, *slower = head;
        while (faster->next != NULL && faster->next->next != NULL) {
            faster = faster->next->next;
            slower = slower->next;
        } //bool odd = faster->next == NULL ? true : false; // 链表长度是否为奇数
        ListNode *head2 = slower, *prior = slower->next, *tail;
        head2->next = NULL;
        while (prior != NULL) { // 逆序后半段链表
            tail = prior->next;
            prior->next = head2->next;
            head2->next = prior;
            prior = tail;
        }
        head2 = head2->next;
        while (head2 != NULL) {
            if (head->val != head2->val)
                return false;
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};

本代码提交AC，用时25MS。

二刷。同样的思路：

class Solution {
public:
	bool isPalindrome(ListNode* head) {
		if (head == NULL || head->next == NULL)return true;
		// 快慢指针
		ListNode *fast = head, *slow = head;
		while (fast != NULL && fast->next != NULL) {
			fast = fast->next->next;
			slow = slow->next;
		}
		// 逆序后半段
		ListNode *dummy = new ListNode(0);
		ListNode *par = slow, *child = slow->next;
		while (par != NULL) {
			child = par->next;
			par->next = dummy->next;
			dummy->next = par;
			par = child;
		}
		// 判断是否相等
		slow = head;
		fast = dummy->next;
		while (fast != NULL) {
			if (slow->val != fast->val)return false;
			slow = slow->next;
			fast = fast->next;
		}
		return true;
	}
};

本代码提交AC，用时28MS。