Problem: 234. 回文链表
文章目录
- 解题方法
- 复杂度
- Code
解题方法
找到链表的中点：首先，我们可以使用快慢指针技巧来找到链表的中点。慢指针每次移动一步，快指针每次移动两步。当快指针到达链表的末尾时，慢指针就会指向链表的中点。
反转后半部分(使用递归反转链表)
比较前半部分和后半部分
复杂度
- 时间复杂度:
时间复杂度, 示例：
- 空间复杂度:
空间复杂度, 示例：
Code
class Solution {
public:
// 思路 ： 使用快慢指针的方法，找到链表的中间结点
// 反转后面的部分，再比较两部分
ListNode* find_midNode(ListNode* head){
if(head == NULL) return NULL ;
if(head->next == NULL ) return head ;
ListNode* slow = head ;
ListNode* fast = head ;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next ;
slow = slow->next ;
}
return slow ;
}
// 使用递归 反转
ListNode* reverse(ListNode* head) {
if(head == NULL || head->next ==NULL) return head;
ListNode* newHead = reverse(head->next) ;
head->next->next = head ;
head->next = nullptr ;
return newHead ;
}
bool isPalindrome(ListNode* head) {
if(head->next == NULL )return true ;
// 找到中间结点
ListNode *mid_node = find_midNode(head) ;
// 反转
ListNode* right = reverse(mid_node) ;
for(ListNode*left = head ; right ; left =left->next, right=right->next) {
if(left->val !=right->val) return false ;
}
return true ;
}
};