随手练——S(n)=O(1),判断一个链表是否为“回文”
2024-10-14 01:08:13
方法一:T(n)=O(n),S(n)=O(n)
走完一遍链表,每个值入栈,之后再走一遍链表,和每次弹出的栈顶进行比较。
核心:
LNode *p = l->next;
while (p) {
s.push(p->data);
p = p->next;
}
p = l->next;
while (p) {
if (p->data != s.top()) {
cout << "fuck" << endl;
break;
}
s.pop();
p = p->next;
}
if (!p)cout << "" << endl;
完整:
#include <iostream>
#include <stack>
using namespace std;
typedef struct LNode {
struct LNode *next;
int data;
}*LinkList;
LinkList init() {
LinkList l = (LinkList)malloc(sizeof(LNode));
l->next = NULL;
return l;
} void push_back(LinkList l,int x) {
LNode *p = l;
LNode *s= (LNode *)malloc(sizeof(LNode));
s->data = x;
while (p->next) {
p = p->next;
}
s->next = p->next;
p->next = s;
} int main() {
int n;
stack<int>s;
LinkList l = init();
cin >> n;
for (int i = ; i < n; i++) {
int t;
cin >> t;
push_back(l, t);
}
LNode *p = l->next;
while (p) {
s.push(p->data);
p = p->next;
}
p = l->next;
while (p) {
if (p->data != s.top()) {
cout << "fuck" << endl;
break;
}
s.pop();
p = p->next;
}
if (!p)cout << "" << endl;
return ;
}
方法二:T(n)=O(n),S(n)=O(n)
用一个鬼畜(二倍速)指针,一个正常指针,当鬼畜指针到最后NULL时,正常指针正好到中间的位置(奇数),或者前半部分最后一个(偶数),然后将后半部分入栈,再一遍进行比较。
核心:
LNode *p = l->next,*pp=l->next;
while (pp&&pp->next) {
p = p->next;
pp = pp->next->next;
}
p = p->next;//数据为偶数的话,p是停在前半部分最后一个,数据为奇数的话,跳过中间一个没问题
while (p) {
s.push(p->data);
p = p->next;
}
p = l->next;
while (!s.empty()) {
if (p->data != s.top()) {
cout << "fuck" << endl;
break;
}
p = p->next; s.pop();
}
if (s.empty())cout << "" << endl;
完整代码:
#include <iostream>
#include <stack>
using namespace std;
typedef struct LNode {
struct LNode *next;
int data;
}*LinkList;
LinkList init() {
LinkList l = (LinkList)malloc(sizeof(LNode));
l->next = NULL;
return l;
} void push_back(LinkList l,int x) {
LNode *p = l;
LNode *s= (LNode *)malloc(sizeof(LNode));
s->data = x;
while (p->next) {
p = p->next;
}
s->next = p->next;
p->next = s;
} int main() {
int n;
stack<int>s;
LinkList l = init();
cin >> n;
for (int i = ; i < n; i++) {
int t;
cin >> t;
push_back(l, t);
}
LNode *p = l->next,*pp=l->next;
while (pp&&pp->next) {
p = p->next;
pp = pp->next->next;
}
p = p->next;//数据为偶数的话,p是停在前半部分最后一个,数据为奇数的话,跳过中间一个没问题
while (p) {
s.push(p->data);
p = p->next;
}
p = l->next;
while (!s.empty()) {
if (p->data != s.top()) {
cout << "fuck" << endl;
break;
}
p = p->next; s.pop();
}
if (s.empty())cout << "" << endl;
return ;
}
方法三:T(n)=O(n),S(n)=O(1)
同样用一个鬼畜(二倍速)指针,一个正常指针,不过这次,对后半部分 链表 进行反转。
从两个方向进行 遍历,到中间结束,这个过程中把原来反转的后半部分链表反转回去。
链表反转:
void reverse(LinkList l) {
LNode *pre = NULL, *p = l->next;
while (p) {
LNode *t = p->next;
p->next = pre;
pre = p;
p = t;
}
l->next = pre;
}
核心:(这里反转是没有头结点的,要注意。代码量稍微长了一点,过段时间看该费点劲了)
LNode *p = l->next,*pp=l->next;
while (pp&&pp->next) {
p = p->next;pp = pp->next->next;
}
p = p->next;//和上一解法相同
LNode *pre = NULL;
while (p) {
LNode *t = p->next;
p->next = pre;
pre = p;
p = t;
}
p = l->next;
LNode *q = pre;
pre = NULL;
while (q) {
if (p->data != q->data) sign = ;//需要反转,不能break
LNode *t = q->next;
q->next = pre;
pre = q;
q = t;
p = p->next;
}
p->next = pre;
完整代码:
#include <iostream>
#include <stack>
using namespace std;
typedef struct LNode {
struct LNode *next;
int data;
}*LinkList; void push_back(LinkList l, int x) {
LNode *p = l;
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = x;
while (p->next) {
p = p->next;
}
s->next = p->next;
p->next = s;
} LinkList init() {
LinkList l = (LinkList)malloc(sizeof(LNode));
l->next = NULL;
int n;
cin >> n;
for (int i = ; i < n; i++) {
int t;
cin >> t;
push_back(l, t);
}
return l;
} int main() {
int n; int sign = ;
LinkList l = init();
LNode *p = l->next,*pp=l->next;
while (pp&&pp->next) {
p = p->next;pp = pp->next->next;
}
p = p->next;//和上一解法相同
LNode *pre = NULL;
while (p) {
LNode *t = p->next;
p->next = pre;
pre = p;
p = t;
}
p = l->next;
LNode *q = pre;
pre = NULL;
while (q) {
if (p->data != q->data) sign = ;//需要反转,不能break
LNode *t = q->next;
q->next = pre;
pre = q;
q = t;
p = p->next;
}
p->next = pre; if (!sign)
cout << "" << endl;
else
cout << "fuck" << endl;
return ;
}
最新文章
- NEST与JSON语法对照 一 match与multi_match
- tomcat配置文件详解
- garbage collection - 垃圾收集
- P1018 乘积最大
- 概念学习(Concept Learning)
- hdu1878 欧拉回路
- C++中的运算符重载注意事项
- 每天一道LeetCode--169.Majority Elemen
- 我的前端之旅--SeaJs基础和spm编译工具运用[图文]
- xslt语法之---基础语法
- 安装VMware Sphere ESXi 5.5
- Android学习笔记__1__Android体系架构
- 对面试题(剑指offer)产生的一些思考。
- QLineEdit 仿QQ签名框
- XXX系统发展综述(SSH+Jquery EasyUI)
- Mahout 模糊kmeans
- IntelliJ IDEA 2016.2 配置Tomcat 运行Web项目
- Steeltoe之Distributed Tracing篇
- LeetCode 34 - 在排序数组中查找元素的第一个和最后一个位置 - [二分][lower_bound和upper_bound]
- FFM及DeepFFM模型在推荐系统的探索及实践
热门文章
- android studio 中由于网络问题,编译错误
- [javaSE] 数据结构(栈)
- Java基础教程(3)--回顾HelloWorld
- 三、hive JavaAPI示例
- ios开发 学习积累20161027~20161031
- MySQL Community Server 5.5.56 ZIP Archive 绿色解压版 window安装步骤
- oracle数据库字符集和客户端字符集(2%)是不同的,字符集转化可能会造成不可预期的后果
- [LeetCode]Longest Palindromic Substring题解(动态规划)
- 关于node npm的一个解决方法
- BZOJ2960:跨平面