建设工程有限公司网站江油市建设局网站

题目描述

给你一个单链表的头节点 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;}