题目大意：检查一个单向链表是不是回文。
Problem:
https://leetcode.com/problems/palindrome-linked-list/description/
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?
Idea:
- use fast / slow pointers to find the middle node and see whether the list has odd/even number of elements.
- Reverse the right half the list, and compare with the left half
E.g.
1->2->3->4->3->2->1->null
fast = null
slow = 4
slow->next = 3
reverse(slow->next)
null<-3<-2<-1 compare with 1->2->3->…
Solution: 1
Time complexity: O(n)
Space complexity: O(1)
C++
|
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 |
class Solution { public: bool isPalindrome(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } // if fast != nullptr, list has odd numbers if (fast) slow = slow->next; slow = reverse(slow); while (slow) { if (slow->val != head->val) return false; slow = slow->next; head = head->next; } return true; } private: ListNode* reverse(ListNode* head) { ListNode* prev = nullptr; ListNode* next = nullptr; while (head) { next = head->next; head->next = prev; prev = head; head = next; } return prev; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
这题是不是先将fast 初始的时候让他等于 head->next，这样就不需要检查odd or even了。一快一慢前进的时候，slow指到的就会是要reverse的head。
如果是这样的话一开始就需要检查 head->next是不是nullptr
if (!head || !head->next) return true;
第一段comment有个typo，应该说这样slow->next就会always是指到要reverse的head。