题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
提示：
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
问题分析
O(1)的时间复杂度---跟n不产生关系
因为链表只能比较当前值和next域的值，因此我们把链表中的值导入到数组当中进行比较。
我的解法：
比较前面和后面的值，两个指针同时往中间走进行比较。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool isPalindrome(struct ListNode* head) {int arr[100000];int index=0;struct ListNode* flag=head;while(flag!=NULL){arr[index]=flag->val;index++;flag=flag->next;}int i=0;int j=index-1;for(;i<j;){if(arr[i]==arr[j]){i++;j--;}else{return false;}}return true;
}另一种解法：
快慢指针能够找到链表中间位置，也能判断链表是否有环。
一个走一步，一个走两步
后面的链表翻转，比较两段链表的值。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool isPalindrome(struct ListNode* head) {if(head==NULL||head->next==NULL){return true;}struct ListNode* slow = head;struct ListNode* fast = head;while(fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;}//后半段翻转struct ListNode* h=NULL;struct ListNode* f=slow;while(f!=NULL){struct ListNode* w=f->next;f->next=h;h=f;f=w;}//比较两个链表while(h!=NULL){if(head->val!=h->val){return false;}head=head->next;h=h->next;}return true;}
