> For the complete documentation index, see [llms.txt](https://dfine.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dfine.gitbook.io/leetcode/234.palindrome_linked_list.md).

# 234.Palindrome Linked List

**234.Palindrome Linked List**

难度:Easy

> 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?
```

可以使用数组保存每个链表的值，完成在O(n)时间内解决，但是空间复杂度为O(n),如果对每个元素，比较相应位置上的值，则可以降到O(1)空间复杂度，但时间复杂度此时为O(n^2).

考虑到反转链表的时间复杂度也是O(n)，所以可以将前半部分反转，然后一一比较。\
需要注意链表长度奇偶情况。

```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        if(!head->next->next) return head->val == head->next->val;
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast->next &&fast->next->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
//Reverse List
   //   cout<<slow->val <<endl;
        ListNode* pre=head;
        ListNode* cur=head->next;
        ListNode* tmp=head->next->next;
        head->next=NULL;
        ListNode* new_head=slow->next;

        if(fast->next)
        {
             slow=slow->next;
        while(cur != slow)
        {
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
           
        }
        else
        {
        while(cur != slow)
        {
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }

        }           cur=pre;

        cout<<cur->val<<endl;
        while(new_head)
        {
            if(new_head->val !=cur->val ) return false;
            new_head = new_head->next;
            cur=cur->next;
        }
        return true;
        
    }
};
```

> 执行用时 :24 ms, 在所有 C++ 提交中击败了93.93%的用户\
> 内存消耗 :12.3 MB, 在所有 C++ 提交中击败了98.15%的用户


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/234.palindrome_linked_list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.