回文链表LeetCode234题
题目描述
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
解题思路
代码实现
//1->2->3->3->2->1
struct ListNode* reverselist(struct ListNode* head)
{
//利用递归将链表逆置
if (head == NULL || head->next == NULL) return head;
struct ListNode* h = reverselist(head->next);
head->next->next = head;
head->next = NULL;
return h;
}
bool isPalindrome(struct ListNode* head) {
if (head == NULL || head->next == NULL) return true;
struct ListNode* fast = head;
struct ListNode* slow = head;
//让慢指针走到链表中间位置
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
slow = reverselist(slow);//逆置后半部分的链表
//比较前半部分的链表和后半部分的链表是否相同
while (slow)
{
if (slow->val != head->val)
{
return false;
}
slow = slow->next;
head = head->next;
}
return true;
}