C++刷LeetCode(面试题 02.06. 回文链表)【翻转链表】
本帖最后由 糖逗 于 2020-7-13 09:43 编辑题目描述:
编写一个函数,检查输入的链表是否是回文的。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
来源:力扣(LeetCode)
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
/**
* 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 == NULL || head -> next == NULL)return true;
//计算链表长度
int count = 0;
ListNode*temp1 = head;
while(temp1){
temp1 = temp1 -> next;
count++;
}
//翻转前半截链表
ListNode*temp2 = head;//注意此处!!!
temp1 = NULL;//注意此处!!!
int len = 1;
while(len <= count / 2){
ListNode*temp = temp2 -> next;
temp2 -> next = temp1;
temp1 = temp2;
temp2 = temp;
len++;
}
//比较前后两段
if(count % 2 == 1)temp2 = temp2 -> next;
while(temp2){
if(temp1->val != temp2->val)return false;
temp1 = temp1->next;
temp2 = temp2->next;
}
return true;
}
};
页:
[1]