php做直播网站,凡科网建站模板,个人域名备案的要求,深圳58网站建设题目描述
给你一个单链表的头节点 head #xff0c;请你判断该链表是否为回文链表。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
提示#xff1a;
链表中节点数目在范围[1, 105] 内0 Node.val 9 进阶#xff1a;你能否用 O(n) 时间…题目描述
给你一个单链表的头节点 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 index0;struct ListNode* flaghead;while(flag!NULL){arr[index]flag-val;index;flagflag-next;}int i0;int jindex-1;for(;ij;){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(headNULL||head-nextNULL){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* hNULL;struct ListNode* fslow;while(f!NULL){struct ListNode* wf-next;f-nexth;hf;fw;}//比较两个链表while(h!NULL){if(head-val!h-val){return false;}headhead-next;hh-next;}return true;}
