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

Follow up:

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

 

 to see which companies asked this question

 

思路：

1.利用快慢两个指针找到中间结点

2.从中间结点下一个结点开始逆置链表，得到新的链表

3.新的链表与原来链表依次比较结点，如有不同，return false

 

思路很清晰，代码直接写在leetcode网站上了，没有调试，一次性AC通过，很有成就感

bool isPalindrome(ListNode* head) {    if (head == nullptr || head->next == nullptr)        return true;    // 寻找中间结点    ListNode *slow = head;    ListNode *fast = head;    while (fast->next != nullptr && fast->next->next != nullptr)    {        slow = slow->next;        fast = fast->next->next;    }    // 逆置后部分链表    ListNode *newList = slow->next;    ListNode *curNode = slow->next->next;    newList->next = nullptr;    while (curNode != nullptr)    {        ListNode *temp = curNode->next;        curNode->next = newList;        newList = curNode;        curNode = temp;    }    // 依次比较    while (newList != nullptr)    {        if (newList->val != head->val)            return false;        newList = newList->next;        head = head->next;    }    return true;}