目录
题目来源:
代码实现:
思路分析:
实现过程:
题目来源:
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
题目描述:
本题的难点在于时间复杂度为O(n),空间复杂度为O(1)。
代码实现:
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head, * slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
struct ListNode* reverse(struct ListNode* head)
{
struct ListNode* prev = NULL, * cur = head, * next = NULL;
while (cur)
{
//尾插
next = cur->next;
cur->next = prev;
prev = cur;
//迭代
cur = next;
}
return prev;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
struct ListNode* mid = middleNode(A);
struct ListNode* rmid = reverse(mid);
while (rmid)
{
if (rmid->val != A->val)
return false;
rmid = rmid->next;
A = A->next;
}
return true;
}
};
思路分析:
因为回文结构是正着读反着读是一样的,因此我们找到链表的中间结点,然后从中间节点开始逆置到尾结点,然后用逆置后的链表与原链表的前半段对比,如果每个结点的 val 都相等,就说明此链表是回文结构。
实现过程:
1.使用快慢指针,初始化都指向原链表的头,慢指针一次走一步,快指针一次走两步,快指针走到空或快指针的 next 走到空时,慢指针指向的就是中间结点。
2.找到中间结点后,从中间结点开始到尾结点进行逆置。
这里讲的不够细致,找中间结点与逆置分别是两篇文章,里面讲的比较细致。
找中间结点:http://t.csdn.cn/z3vm5
逆置链表/反转链表:http://t.csdn.cn/Jt38p
我们分别将这两个功能封装成函数使用。
3.以逆置之后的链表头结点作为循环条件(这里其实不难发现逆置后的链表与原链表的长度相等),遍历整个逆置之后的链表,与原链表的 val 对比,如果存在哪个结点的val 不相等就返回 false,如果遍历完整个逆置后的链表都相等就返回 true。
这样的解法可以实现题目的要求:本题的难点在于时间复杂度为O(n),空间复杂度为O(1)。
如果大牛的您看到有什么问题留言给我,我一定会认真看的,谢谢您。如果您看了觉得有收获,关注 + 点赞支持一下呗。文章来源:https://www.toymoban.com/news/detail-458316.html
*** 本篇结束 ***文章来源地址https://www.toymoban.com/news/detail-458316.html
到了这里,关于【链表OJ题 6】链表的回文结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!