考点
题解
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
| class Solution { private: bool judgeFunc(ListNode* head, ListNode* midNode) { for (ListNode *left = head, *right = midNode->next; right != nullptr; left = left->next, right = right->next) { if (left->val != right->val) return false; } return true; }
ListNode* reverseList(ListNode* dummyHead) { ListNode *tail = dummyHead->next; while (tail->next != nullptr) { ListNode *node = tail->next; tail->next = node->next; node->next = dummyHead->next; dummyHead->next = node; } return dummyHead; }
ListNode* findMid(ListNode* head) { ListNode *slow = head, *fast = head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; }
public: bool isPalindrome(ListNode* head) { if (head->next == nullptr) return true; return (judgeFunc(head, reverseList(findMid(head)))); } };
|
思路
验证回文串,最直接的方法就是双指针,左指针从头向尾遍历,右指针从尾向头遍历,只要两个指针指向的值不一样就肯定不是回文串
子问题:两个指针反向遍历,比较两个指针指向的值
递归语句顺序:递归方向分为一去一回,去方向到达临界点后返回;这里只能在回方向操作,因为右指针需要从尾向头遍历
左指针怎么办呢?额外单独设置一个成员变量即可,待右指针开始从尾向头遍历时再做比较
返回值:不需要返回值
临界点:右指针为空
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { private: bool ans; ListNode *left; void recursiveFunc(ListNode *right) { if (right == nullptr) return; recursiveFunc(right->next); if(left->val != right->val) ans = false; left = left->next; }
public: bool isPalindrome(ListNode* head) { left = head; ans = true; recursiveFunc(head); return ans; } };
|
但题目要求只能以常数空间复杂度运行,故而不能使用递归;用迭代分为以下几个步骤
- 找到链表中心点,分为左、右两个子链表
- 右子链表反转
- 即可对左、右两个子链表进行同向比较了
这里有一个可有可无的Trick
如果是奇数个链表节点,比如{1, 2, 3, 4, 5}
,找到的链表中心点是3
如果是偶数个链表节点,比如{1, 2, 3, 4}
,则找到的链表中心点应为2
这样中心点就可以作为右子链表的dummyHead
,便于反转