【C语言】234.回文链表【LeetCode】

简介: 【C语言】234.回文链表【LeetCode】

ઇଓ 欢迎来阅读子豪的博客(LeetCode刷题篇)


☾ ⋆有什么宝贵的意见或建议可以在留言区留言


ღღ欢迎 素质三连 点赞 关注 收藏


❣ฅ码云仓库:补集王子 (YZH_skr) - Gitee.com

234. 回文链表 - 力扣(LeetCode)

https://leetcode.cn/problems/palindrome-linked-list/


59a4289e8ee54a4093bec406e07f7ae4.png


找中间结点 然后逆置


最后一个指针判断奇偶结点


奇数个结点


80e50d9cd4f842ccaf25427900d0df3a.png


偶数个结点


让mid(中间结点指向中间偏后一个)


663870b192c846c9be4ef0b3dfd949d4.png


快慢指针,获取到中间节点(slow)


4801e1ee285645ba8e5df3d239d93422.png


从中间节点开始翻转后一半链表


dc046d3b75774d2eb3ec6da70aa86576.png


struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}


比较


469af6208fb3417ba75389c70dec2d72.png


代码


struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // 快慢指针,获取到中间节点,从中间节点开始翻转后一半链表
        struct ListNode* slow, *fast, *mid, *cur;
        slow = fast = A;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow ->next;
        }
        if(fast != NULL)
        slow = slow->next;
        mid = slow;
        cur = reverseList(mid);
        while(cur->next != NULL)
        {
            if(A->val != cur->val)
                return false;
                cur = cur->next;
                A = A->next;
        }
        return true;
    }
};


补充:侵入式编程:破坏了原来的结构


总结


本题要考虑几个因素


1,访问越界问题


2,如何比较


3,奇偶个结点


总之还是要多画图,现实中多画图,才有思路

相关文章
|
1月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
35 1
|
21天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
48 4
|
1月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
1月前
|
存储 缓存 C语言
C语言:链表和数组有什么区别
C语言中,链表和数组是两种常用的数据结构。数组是一种线性结构,元素在内存中连续存储,通过下标访问,适合随机访问且大小固定的情况。链表由一系列不连续的节点组成,每个节点存储数据和指向下一个节点的指针,适用于频繁插入和删除操作的场景,链表的大小可以动态变化。
|
1月前
|
C语言
无头链表再封装方式实现 (C语言描述)
如何在C语言中实现无头链表的再封装,包括创建节点和链表、插入和删除操作、查找和打印链表以及销毁链表的函数。
27 0
|
1月前
|
C语言
C语言链式结构之有头单链表再封装写法
本文介绍了如何使用C语言对有头单链表进行封装,包括节点的创建、链表的初始化、数据的插入和删除,以及链表的打印等功能。
17 1
|
1月前
|
C语言
C语言结构体链式结构之有头单链表
文章提供了一个C语言实现的有头单链表的完整代码,包括创建链表、插入、删除和打印等基本操作。
23 1
|
21天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
39 0
|
1月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
18 0
LeetCode第二十四题(两两交换链表中的节点)
|
1月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
78 0