数据结构 --- 单链表 oj 问题:链表的回文结构
最编程
2024-10-07 20:55:30
...
目录
题目要求
手搓简易单链表
代码实现
题目要求
对于一个单链表,设计一个时间复杂度为O(N),空间复杂度为O(1)的算法,判断其是否为回文结构,给定一个链表的头指针 head,返回一个 bool 值,代表其是否为回文结构
举例说明:
链表:1->2->3->2->1
返回:true
链表:1->2->3->1
返回:false
手搓简易单链表
代码演示:
struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);
struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n6);
struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n7);
struct ListNode* n8 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n8);
n1->val = 1;
n2->val = 2;
n3->val = 3;
n4->val = 4;
n5->val = 4;
n6->val = 3;
n7->val = 2;
n8->val = 1;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n6;
n6->next = n7;
n7->next = n8;
n8->next = NULL;
代码实现
代码演示:
// 找到中间节点
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// 逆置链表(头插法)
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL)
return NULL;
struct ListNode* rhead = NULL;
struct ListNode* cur = head;
struct ListNode* next = cur->next;
while (cur != NULL)
{
cur->next = rhead;
rhead = cur;
cur = next;
if (next != NULL)
next = next->next;
}
return rhead;
}
// 链表的回文结构
bool chkPalindrome(struct ListNode* head)
{
if (head == NULL)
return true;
// 找到中间节点
struct ListNode* mid = middleNode(head);
// 从中间节点逆置
struct ListNode* rmid = reverseList(mid);
struct ListNode* cur = head;
while (rmid != NULL)
{
if (cur->val != rmid->val)
return false;
cur = cur->next;
rmid = rmid->next;
}
return true;
}
代码解析:
先找到单链表的中间节点 mid ,再从中间节点开始往后逆置节点,cur 节点指针和 rmid 节点指针同时往后走,只要val 不同时就表示不是回文结构,返回 false ,如果一直没有返回,那么就代表链表是回文结构,返回 true
代码验证:
算法的时间和空间复杂度:
时间复杂度(大O渐进表示法):O(N)
空间复杂度(大O渐进表示法):O(1)
上一篇: 大数据]Flink CDC 实时同步 mysql 数据
下一篇: 贪心算法c++
推荐阅读
-
数据结构 --- 单链表 oj 问题:链表的回文结构
-
【数据结构】04.单链表-三、链表的分类
-
了解阎维文《数据结构》中的单链表 LNode 和 *LinkList
-
数据结构与算法(II)--单链表的线性表 顺序存储和链式存储
-
[数据结构入门] 10 个强力扣链表 OJ 问题图解详解
-
数据结构》学习笔记 - 链表知识(有头节点和无头节点单链表的基本操作)(回顶部)
-
Java 数据结构 - 线性表 - 单链表应用 - 单链表的逆运算
-
链表的回文结构OJ
-
数据结构]单链表解释 + 完整代码(插入、删除、尾部插入、头部插入、按值和按位查找、前向插入和后向插入),包含和不包含头部节点的两种实现方式
-
数据结构 - 单链表的基本操作(表头插入、表尾插入)