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