LeetCode: 234. Palindrome Linked List

发表于 | 分类于

题目描述

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

Example 1:

1
2
Input: 1->2
Output: false

Example 2:

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

Follow up:
Could you do it in O(n) time and O(1) space?

O(1)的空间复杂度，言外之意就是不借用数组等工具来做，那么最先想到的还是快慢指针。使用快指针来探索是否链表遍历到了头，慢指针来确定链表的中间位置。由于还要进行比较，所以在慢指针进行遍历的时候，需要把链表反转，方便之后的比较工作。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head;
        if (slow == NULL or slow->next == NULL)
            return true;

        ListNode* fast = head->next;
        ListNode* last = NULL;
        ListNode* tmp = NULL;
        int flag = 0;

        while (fast->next != NULL) {
            fast = fast->next;
            if (fast->next == NULL) {
                flag = 1;
                break;
            }

            tmp = slow->next;
            slow->next = last;
            last = slow;
            slow = tmp;
            fast = fast->next;

        }

        fast = slow->next;
        if (flag)
            fast = fast->next;
        slow->next = last;
        while (slow != NULL) {
            if (slow->val != fast->val)
                return false;
            slow = slow->next;
            fast = fast->next;
        }

        return true;
    }
};