Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* func(ListNode* head) { if(head->next != NULL) { ListNode *tail = func(head->next); tail->next = head; head->next = NULL; } return head; } ListNode* reverseList(ListNode* head) { if(head == NULL || head->next == NULL) return head; ListNode *newhead = head; while(newhead->next != NULL) { newhead = newhead->next; } func(head); return newhead; } bool isPalindrome(ListNode* head) { if(head == NULL || head->next == NULL) return true; ListNode *p, *q; p = head; q = head; while(q != NULL) { p = p->next; q = q->next; if(q != NULL) { q = q->next; } } p = reverseList(p); while(p != NULL) { if(head->val != p->val) return false; else { head = head->next; p = p->next; } } return true; } }; |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
