零元创业加盟网_长沙斌网网络_网站优化公司推荐_互联网营销模式

题目

https://leetcode.cn/problems/aMhZSa/submissions/597864785

给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

示例 1：

输入: head = [1,2,3,3,2,1]
输出: true

示例 2：

输入: head = [1,2]
输出: false

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/bool isPalindrome(struct ListNode* head) {}

思路

1. 找到中间节点
2. 从中间节点开始，对后半段逆置
3. 前半段和后半段比较

代码

//逆置
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head, *newnode = NULL;while (cur){struct ListNode* next = cur->next;cur->next = newnode;newnode = cur;cur = next;}return newnode;
}
//中间节点
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow, *fast;slow = fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
bool isPalindrome(struct ListNode* head){struct ListNode* mid = middleNode(head);struct ListNode* rhead = reverseList(mid);while (rhead){if (head->val != rhead->val)return false;head = head->next;rhead = rhead->next;}return true;
}