速通数据结构链表代码题
2023-12-21 11:37:36
链表
- 头文件
- 设计一个递归算法，删除不带头节点的单链表L中所有值为x的结点
- 删除带头节点单链表中所有值为x的结点
- 删除带头结点单链表中第一个值为x的结点
- 从尾到头反向输出每个单链表的值
- 编写一个算法让单链表就地逆置
- 从链表中删除给定值在s到t之间的所有元素(不包括s和t)
- 删除带头节点的单链表中最小值
- 删除不带头节点的单链表中最小的元素
- 给定一个单链表，按递增排序输出的单链表中各结点的数据元素，并释放节点所占空间
- 将一个带头节点的单链表A分解成两个带头节点的单链表A和B使A中含奇数位置元素，B中含偶数位置元素，且相对位置不变
- 将一个单链表{a1,b1,a2,b2……an,bn}拆分成{a1,a2,……,an}和{bn,bn-1,……,b1}
- 删除递增链表中重复的元素 并且保留这些重复的元素的其中一个
- 两个递增有序的单链表, 设计算法成一个非递减有序的链表
- 两个递增有序的单链表 设计算法成一个非递增有序的链表
- A, B两个单链表递增有序，从A,B中找出公共元素产生单链表C，要求不破环A,B结点
- A, B两个单链表递增有序，从A，B中找出公共元素并存放于A
- 两个序列分别为A、B，将其存放到链表中, 判断B是否是A的连续子序列
- 查找单链表中倒数第k个结点，若成功，则输出该节点的data，并返回1，否则返回0
- 用单链表保存m个整数，并且|data|≤n, 要求设计时间复杂度尽可能高效的算法 对于data绝对值相等的点，仅保留第―次出现的点
- 判断带头结点的循环双链表是否对称
- 有两个循环单链表，链表头指针分别为h1,h2,试编写函数将h2链表接到h1之后,要求链接后仍保持循环链表形式
- 设有一个带头结点的循环单链表，其结点值为正整数设计算法反复找出链表内最小值并不断输出,并将结点从链表中删除,直到链表为空，再删除表头结点
- 判断单链表是否有环
- 给定一个单链表L(a1,a2,a3,……,an)将其重新排列为(a1,an,a2,an-1,……)
头文件
#include <iostream>
using namespace std;
typedef struct LNode
{
int data;
struct LNode *next;
} LNode, *Linklist;
//不带头节点的链表
Linklist aaaa();
//带头节点的链表
Linklist bbbb();
#include <iostream>
using namespace std;
//循环单链表
typedef struct LNode
{
int data;
struct LNode *next;
} LNode, *Linklist;
Linklist dddd();
#pragma once
#include <iostream>
using namespace std;
//循环双链表
typedef struct DNode
{
int data;
struct DNode *next, *prior;
} DNode, *Dinklist;
Dinklist cccc();
#include"linklist.h"
//不带头节点的链表
Linklist aaaa()
{
LNode *L = new LNode;
int a;
cin >> a;
L->data = a;
LNode *p = L; //声明一个指针指向头结点，
//生成链表
cin >> a;
while (a != 0)//输入0为循环的结束条件
{
LNode *q = new LNode;
q->data = a;
q->next = NULL;
p->next = q;
p = p->next;
cin >> a;
}
p->next = NULL;
return L;
}
//带头节点的链表
Linklist bbbb()
{
LNode *L = new LNode; //创建一个头结点
LNode *p = L; //声明一个指针指向头结点
//生成链表
int a;
cin >> a;
while (a != 0)
{
LNode *q = new LNode;
q->data = a;
q->next = NULL;
p->next = q;
p = p->next;
cin >> a;
}
p->next = NULL;
return L;
}
#include"circlesinglefun.h"
Linklist dddd()
{
LNode *L = new LNode;
LNode *p = L;
int a;
cin >> a;
while (a != 0)
{
LNode *q = new LNode;
q->data = a;
q->next = NULL;
p->next = q;
p = p->next;
cin >> a;
}
p->next = L;
return L;
}
#include"circledoublefun.h"
Dinklist cccc() {
DNode *L = new DNode;
DNode *p = L;
int a;
cin >> a;
while (a != 0)
{
DNode *q = new DNode;
q->data = a;
q->next = NULL;
q->prior = p;
p->next = q;
p = p->next;
cin >> a;
}
p->next = L;
L->prior = p;
return L;
}
设计一个递归算法，删除不带头节点的单链表L中所有值为x的结点
#include <iostream>
using namespace std;
#include"linklist.h"
/*
设计一个递归算法，删除不带头节点的单链表L中所有值为x的结点
5 2 4 6 2 0 0为for循环结束的标志
5 4 6
*/
void del_x(LNode *&L, int x)//删除操作 参数是链表和要删除的结点的值
{
LNode *p;
if (L == NULL) return;
if (L->data == x)
{
p = L;//记录位置
L = L->next;//后移操作 进行第二轮递归的操作时候 L->next=L->next->next
free(p);
del_x(L, x);
}
else
del_x(L->next, x);//递归函数 这里是不会断链的 (将L->next带入上述的操作时候)
}
int main01()
{
LNode *L = aaaa();
del_x(L, 2);
while (L != NULL)
{
cout << L->data << " ";
L = L->next;
}
return EXIT_SUCCESS;
}
/*
为什么这段代码不会导致链表断链呢？因为在递归过程中，只有当满足条件（L->data == x）时，才进行删除操作，并在删除操作之后再次递归调用del_x(L, x)，这样保证了删除节点后，将正确的下一个节点连接到当前节点，不会造成链表断链。而对于不满足条件的节点，直接通过递归调用del_x(L->next, x)进行下一个节点的处理，也不会引起链表断链
*/
删除带头节点单链表中所有值为x的结点
#include <iostream>
using namespace std;
#include"linklist.h"
/*
删除带头节点单链表中所有值为x的结点
删除结点的话 要知道链表的前一个结点才能删除
p
头节点-->3-->4-->7-->4
p q
头节点-->3-->4-->7-->4
*/
//方法1
void del(LNode *&L, int x)
{
LNode *p = L->next, *pre = L;//初始化
LNode *q;
while (p != NULL)
{
if (p->data == x)
{
q = p;//用q来保存要删除元素的地址 进行删除操作 p是要用来后面进行遍历
pre->next = p->next;
p = p->next;//继续往后遍历
free(q);
}
else
{
pre = p;
p = p->next;
}
}
}
//方法2
void Del(LNode *&L, int x)
{
LNode *p = L;
while (p->next != NULL)
{
if (p->next->data == x)
{
LNode *q = p->next;
p->next = q->next;
free(q);
}
else
p = p->next;
}
}
int main02()
{
LNode *L = bbbb();
Del(L, 4);
LNode *q = L->next;
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return EXIT_SUCCESS;
}
删除带头结点单链表中第一个值为x的结点
#include <iostream>
#include "linklist.h"
using namespace std;
/*
删除带头结点单链表中第一个值为x的结点
3 4 2 3 2 2 2
3 4 3 2 2 2
*/
//方法1
int finddelete(LNode *&C, int x)
{
LNode *p, *q;
p = C;
while (p->next != NULL)
{
if (p->next->data == x)
break;
//break语句执行后 此时的p保留到下一次的操作、
//执行break语句后，栈区的数据不会被立即释放。在程序执行到break语句时，会跳出当前循环并继续执行循环之后的代码，但是栈上的数据仍然存在，并且可以在后续代码中继续访问
else
p = p->next;
}
if (p->next == NULL)//到底了
return 0;
else
{
q = p->next;
p->next = q->next;
free(q);
return 1;
}
}
//方法2
void finddelete2(LNode *&C, int x)
{
LNode *p, *q;
p = C;
while (p->next != NULL)
{
if (p->next->data == x)
{
q = p->next;
p->next = q->next;
free(q);
return;
}
else
p = p->next;
}
return;
}
int main03()
{
LNode *L = bbbb();
//finddelete(L, 2);
finddelete2(L, 2);
LNode *q = L->next;
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return 0;
}
从尾到头反向输出每个单链表的值
#include <iostream>
#include "linklist.h"
using namespace std;
/*
从尾到头反向输出每个单链表的值
递归
思想:将除了第一个结点的结点反向输出，然后再输出第一个结点
弱智
3 8 7 2
2 7 8 3
*/
void print(LNode *L)
{
if (L->next != NULL)
{
print(L->next);
}
cout << L->data << " ";
}
int main04()
{
LNode *L = bbbb();
print(L->next);//递归操作
return EXIT_SUCCESS;
}
编写一个算法让单链表就地逆置
#include <iostream>
#include "linklist.h"
using namespace std;
/*
编写一个算法让单链表就地逆置
1、头插法
2、三指针法 让链表的结点依次变为 第一个结点的next指向null 5-->3 2-->5 10-->2 最后头节点指向10
L-->3-->5-->2-->10
L-->10-->2-->5-->3
*/
//方法1 头插法
void reverse(LNode *&L)
{
LNode *p = L->next, *r;//r是用来记录p之后的下一个结点
L->next = NULL;//头节点的next指针指向null 用于进行头插
while (p != NULL)
{
r = p->next;
p->next = L->next;
L->next = p;
p = r;//头插法 执行完了之后p的next指针指向的是null，因此需要r指针来记录原来的链表的p的next指针域指向的结点
}
}
//方法2 三指针
void Reverse(LNode *&L)
{
LNode *p = L->next, *r = p->next;
LNode *pre;//初始值是p的位置 是用来记录p的前一个结点 用于怕p->next=pre
p->next = NULL;//将第一个结点的next指针域指向置为null 作为出口
while (r != NULL)
{
pre = p;
p = r;
r = r->next;
p->next = pre;
}
L->next = p;
}
int main05()
{
LNode *L = bbbb();
reverse(L);
LNode *q = L->next;
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return 0;
}
从链表中删除给定值在s到t之间的所有元素(不包括s和t)
#include <iostream>
#include "linklist.h"
using namespace std;
/*
从链表中删除给定值在s到t之间的所有元素(不包括s和t)
3 6 19 8 7 10 5
3 19 10 5
*/
void del(LNode *&L, int min, int max)
{
LNode *p = L;
while (p->next != NULL)
{
if (p->next->data > min && p->next->data < max)
{
LNode *u = p->next;//指针u 便于删除
p->next = u->next;
free(u);
}
else
p = p->next;
}
}
int main06()
{
LNode *L = bbbb();
del(L, 5, 10);
LNode *q = L->next;
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return EXIT_SUCCESS;
}
删除带头节点的单链表中最小值
/*
删除带头节点的单链表中最小值
L-->4 10 2 12 7
L-->4 10 12 7
*/
#include <iostream>
#include "linklist.h"
using namespace std;
void del_min2(LNode *&L)
{
LNode *p = L;
LNode *minp = L;
while (p->next != NULL)
{
//第一次是不满足这个条件的 p往后移动
if (p->next->data < minp->next->data)
minp = p;
p = p->next;
}
LNode *u = minp->next;
minp->next = u->next;
free(u);
}
int main07()
{
LNode *L = bbbb();
del_min2(L);
LNode *q = L->next;
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return 0;
}
删除不带头节点的单链表中最小的元素
#include <iostream>
#include"linklist.h"
using namespace std;
/*
删除不带头节点的单链表中最小的元素
*/
void del_min(LNode *&L)
{
LNode *minp = L;
LNode *p = L->next;
while (p != NULL)
{
if (p->data < minp->data)
minp = p;
p = p->next;
}
if (L == minp)
{
L = L->next;
free(minp);
return;
}
p = L;
while (p->next != minp)
p = p->next;
p->next = minp->next;
free(minp);
}
int main08()
{
LNode *L = aaaa();
del_min(L);
LNode *q = L;
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return 0;
}
给定一个单链表，按递增排序输出的单链表中各结点的数据元素，并释放节点所占空间
#include <iostream>
#include "linklist.h"
using namespace std;
/*
给定一个单链表，按递增排序输出的单链表中各结点的数据元素，并释放节点所占空间
1、依次找到这个单链表最小的元素
2、依次进行释放操作
3 4 2 1 5
1 2 3 4 5
*/
void del_min10086(LNode *&head)
{
while (head->next != NULL)//循环条件 head后面为null时 循环结束
{
LNode *pre = head;
LNode *p = head->next;
while (p->next != NULL)
{
if (p->next->data < pre->next->data)
{
pre = p;
}
p = p->next;
}
cout << pre->next->data << " ";
LNode *u = pre->next;//u记录最小的元素
pre->next = u->next;
free(u);
}
free(head);
}
int main09()
{
LNode *L = bbbb();
del_min10086(L);
return EXIT_SUCCESS;
}
将一个带头节点的单链表A分解成两个带头节点的单链表A和B使A中含奇数位置元素，B中含偶数位置元素，且相对位置不变
/*
堆区申请一个数组
c语言 int *A=(int *)malloc(sizeof(int)*n)
c++ int *A=new int[n]
*/
#include<iostream>
using namespace std;
#include"linklist.h"
/*
奇偶链表 这里的奇偶是数组下标的奇偶
将一个带头节点的单链表A分解成两个带头节点的单链表A和B
使A中含奇数位置元素，B中含偶数位置元素，且相对位置不变
L-->4-->10-->7-->6-->15
A-->4-->7-->15
B-->10-->6
*/
Linklist create1(LNode *&A)
{
LNode *B = new LNode;//堆区申请一个结点
//c语言写法 LNode *B = (LNode*)malloc(sizeof(LNode));
B->next = NULL;//将新建立的结点的next域置空
LNode *ra = A, *rb = B, *p = A->next;//p记录A的头节点的下一个结点
A->next = NULL;
while (p != NULL)
{
ra->next = p;
ra = p;
p = p->next;
rb->next = p;
rb = p;
//p = p->next; err 奇数链表的时候 p最后指向的是null null是没有next域的
//偶数链表的时候不需要这样写if
if (p != NULL)
p = p->next;
}
ra->next = NULL;//奇数链表的时候ra->next=null本来就是存在的 偶数链表的时候要进行说明
return B;
}
int main10()
{
LNode *A = bbbb();
LNode *B = create1(A);
LNode *q = A->next;
LNode *p = B->next;
cout << "A: ";
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
cout << endl;
cout << "B: ";
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
return EXIT_SUCCESS;
}
将一个单链表{a1,b1,a2,b2……an,bn}拆分成{a1,a2,……,an}和{bn,bn-1,……,b1}
#include <iostream>
#include "linklist.h"
using namespace std;
/*
将一个单链表{a1,b1,a2,b2……an,bn}拆分成{a1,a2,……,an}和{bn,bn-1,……,b1}
由题意得这个单链表是偶数个
拆分的第一个是奇链表，拆分的第二个是逆序的偶链表（用头插法来进行表示)
*/
Linklist create(LNode *&A)
{
LNode *B = new LNode;
B->next = NULL;
LNode *ra = A, *p = A->next, *q;
A->next = NULL;
while (p != NULL)
{
ra->next = p;
ra = p;
p = p->next;
q = p;
if (q == NULL)//如果是奇数链表的时候加上这句话 偶数则不用加入 指向null的时候就不需要进行头插了
break;//??
p = p->next;
q->next = B->next;
B->next = q;
}
ra->next = NULL;//把A链表断开
return B;
}
int main11()
{
LNode *A = bbbb();
LNode *B = create(A);
LNode *q = A->next;
LNode *p = B->next;
cout << "A ";
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
cout << "B ";
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
return 0;
}
删除递增链表中重复的元素 并且保留这些重复的元素的其中一个
#include <iostream>
#include "linklist.h"
using namespace std;
/*
删除递增链表中重复的元素 并且保留这些重复的元素的其中一个
3 4 4 4 5 5
3 4 5
*/
void del111(LNode *&L)
{
LNode *p = L->next;//指向第一个有元素的位置
//LNode *q;
if (p == NULL)
return;
while (p->next != NULL)
{
LNode* q = p->next;//指向第二个有元素的位置 保持在p的后一个位置就好了
if (p->data == q->data)
{
p->next = q->next;
free(q);
}
else
p = p->next;
}
}
int main12()
{
LNode *A = bbbb();
del111(A);
LNode *q = A->next;
cout << "A ";
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return EXIT_SUCCESS;
}
两个递增有序的单链表, 设计算法成一个非递减有序的链表
#include <iostream>
#include "linklist.h"
using namespace std;
/*
两个递增有序的单链表, 设计算法成一个非递减有序的链表
A-->2-->5-->9-->13
B-->4-->7
*/
void fun10(LNode *&A, LNode *&B)
{
LNode *p = A->next, *q = B->next;
LNode *ra = A;//假设A为合并之后的链表
A->next = NULL;
B->next = NULL;
while (p != NULL && q != NULL)
{
if (p->data <= q->data)
{
ra->next = p;
//ra = p;
//p = p->next;
p = p->next;
ra = ra->next;
}
else
{
ra->next = q;
q = q->next;
ra = ra->next;
}
}
//两个链表之间的长度可能会不相等
if (p != NULL)
ra->next = p;
if (q != NULL)
ra->next = q;
}
int main13()
{
cout << "A:";
LNode *A = bbbb();
cout << "B:";
LNode *B = bbbb();
fun10(A, B);
LNode *q = A->next;
cout << "A+B:";
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return EXIT_SUCCESS;
}
两个递增有序的单链表 设计算法成一个非递增有序的链表
#include <iostream>
#include "linklist.h"
using namespace std;
/*
两个递增有序的单链表 设计算法成一个非递增有序的链表
头插法
A--2--5--9--13
B--4--7
*/
void fun23(LNode *&A, LNode *&B)
{
LNode *p = A->next, *q = B->next, *s;
A->next = NULL;
B->next = NULL;
while (p != NULL && q != NULL)
{
if (p->data <= q->data)
{
s = p;
p = p->next;
s->next = A->next;
A->next = s;
}
else
{
s = q;
q = q->next;
s->next = A->next;
A->next = s;
}
}
while (p != NULL)
{
s = p;
p = p->next;
s->next = A->next;
A->next = s;
}
while (q != NULL)
{
s = q;
q = q->next;
s->next = A->next;
A->next = s;
}
}
int main14()
{
cout << "A:";
LNode *A = bbbb();
cout << "B:";
LNode *B = bbbb();
fun23(A, B);
LNode *q = A->next;
cout << "A:";
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return 0;
}
A, B两个单链表递增有序，从A,B中找出公共元素产生单链表C，要求不破环A,B结点
#include <iostream>
#include "linklist.h"
using namespace std;
/*
A, B两个单链表递增有序，从A,B中找出公共元素产生单链表C，要求不破环A,B结点
1 3 4 5
3 4 5
这题是要新建结点的 不需要free原来的结点
3 4 5
*/
Linklist common(LNode *A, LNode *B)
{
LNode *p = A->next;
LNode *q = B->next;
LNode *C = new LNode;//创一个头节点
LNode *r = C;// , *s;
while (p != NULL && q != NULL)
{
if (p->data < q->data)//p小p右移
p = p->next;
else if (p->data > q->data)//q小q右移
q = q->next;
else//相等的情况
{
LNode* s = new LNode;
s->data = p->data;
r->next = s;
r = s;
p = p->next;//继续往后找
q = q->next;
}
}
r->next = NULL;
return C;//要返回头节点 因此需要定义r指针来指针C进行操作
}
int main15()
{
cout << "A:";
LNode *A = bbbb();
cout << "B:";
LNode *B = bbbb();
LNode *C = common(A, B);
LNode *q = C->next;
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return 0;
}
A, B两个单链表递增有序，从A，B中找出公共元素并存放于A
#include <iostream>
#include "linklist.h"
/*
A, B两个单链表递增有序，从A，B中找出公共元素并存放于A
A 4 6 7 10 19
B 3 4 7 9
A 4 7
*/
using namespace std;
void Union(LNode *&A, LNode *&B)
{
LNode *p = A->next;
LNode *q = B->next;
LNode *ra = A, *u;//ra时刻处于最后一个结点的位置
while (p != NULL && q != NULL)
{
if (p->data < q->data)
{
u = p;
p = p->next;
free(u);
}
else if (p->data > q->data)
{
u = q;
q = q->next;
free(u);
}
else
{
ra->next = p;//连接
ra = p;
p = p->next;//后移进行比较
u = q;
q = q->next;
free(u);
}
}
while (p != NULL)
{
u = p;
p = p->next;
free(u);
}
while (q != NULL)
{
u = q;
q = q->next;
free(u);
}
ra->next = NULL;
free(q);
}
int main16()
{
cout << "A:";
LNode *A = bbbb();
cout << "B:";
LNode *B = bbbb();
Union(A, B);
LNode *q = A->next;
while (q != NULL)
{
cout << q->data << " ";
q = q->next;
}
return 0;
}
两个序列分别为A、B，将其存放到链表中, 判断B是否是A的连续子序列
#include <iostream>
#include "linklist.h"
using namespace std;
/*
两个序列分别为A、B，将其存放到链表中, 判断B是否是A的连续子序列
A 3 7 9 12
B 7 9 12
B是A的连续子序列 序列为7 9 12
A 4 15 10 4 15
B 4 15 1
无子序列
*/
int seq(LNode *A, LNode *B)
{
LNode *p = A->next;
LNode *pre = p;//是用来进行匹配失败操作时所定义的指针 因为匹配失败更新p的位置
LNode *q = B->next;//初始匹配的位置
while (p != NULL && q != NULL)
{
if (p->data == q->data)
{
p = p->next;
q = q->next;
}
else
{
//方法二
//p = p->next;
pre = pre->next;//匹配失败后从下一个结点开始
p = pre;//p移动到pre的位置
q = B->next;//q从头开始匹配
}
}
if (q == NULL)//匹配成功
return 1;
else
return 0;
}
int main17()
{
cout << "A:";
LNode *A = bbbb();
cout << "B:";
LNode *B = bbbb();
cout << "A:" << seq(A, B);
return 0;
}
查找单链表中倒数第k个结点，若成功，则输出该节点的data，并返回1，否则返回0
#include <iostream>
#include "linklist.h"
using namespace std;
/*
查找单链表中倒数第k个结点，若成功，则输出该节点的data，并返回1，否则返回0
1、双指针
2、暴力解法
4 10 6 8
*/
//法一标准解
int find(LNode *head, int k)
{
LNode *q = head->next;
LNode *p = head;
int i = 1;//i用来记录p和q之间的距离 初始值为1
while (q->next != NULL)
{
q = q->next;
++i;
//if (i >= k)//为了保证p和q之间的距离为k 距离为k时候 在同时后移的情况就能解决此题
// p = p->next;
}
while (i >= k) {//为了保证p和q之间的距离为k 距离为k时候 在同时后移的情况就能解决此题
p = p->next;
--i;
}
//while (q != head->next)
//{
// p = p->next;
// q = q->next->next;
// ++i;
//}
if (p == head)
return 0;
else
{
cout << "倒数第3个节点为：" << p->data << endl;
return 1;
}
}
//法二暴力解
//倒数第k个结点就是正数第n-k+1个结点
int len(LNode *L)
{
LNode *p = L->next;
int n = 0;
while (p != NULL)
{
p = p->next;
++n;
}
cout << "n=" << n << endl;
//return n;//返回的是结点的个数
}
int Find(LNode *L, int k)
{
int i = 0, m;
m = len(L) - k + 1;
if (m <= 0)
{
return 0;
}
while (i < m)//正数第几个 如果0<2 就往后移动两次 就是正数第二个
{
L = L->next;
++i;
}
cout << L->data;
return 1;
}
int main()
{
LNode *L = bbbb();
int j = find(L, 3);
//len(L);
cout << "j=" << j << endl;
return 0;
}
用单链表保存m个整数，并且|data|≤n, 要求设计时间复杂度尽可能高效的算法 对于data绝对值相等的点，仅保留第―次出现的点
/*
用单链表保存m个整数，并且|data|≤n, 要求设计时间复杂度尽可能高效的算法
对于data绝对值相等的点，仅保留第―次出现的点
4 -3 -4 2 -3
空间换时间
4 -3 2
*/
#include <iostream>
#include "linklist.h"
using namespace std;
void fun(LNode *&head, int n)
{
LNode *p = head;
LNode *r;
int *q = new int[n + 1];
int m;//存储数据
for (int i = 0; i < n + 1; ++i)
q[i] = 0;
while (p->next != NULL)
{
if (p->next->data > 0)
m = p->next->data;
else
m = -p->next->data;
//在数组中记数 如果绝对值相等的数出现了记为1 如果又出现了则删除后面一个
if (q[m] == 0)
{
q[m] = 1;
p = p->next;
}
else
{
//删除操作
r = p->next;
p->next = r->next;
free(r);
}
}
free(q);
}
int main19()
{
LNode *L = bbbb();
fun(L, 50);
L = L->next;
while (L != NULL)
{
cout << L->data << " ";
L = L->next;
}
return EXIT_SUCCESS;
}
判断带头结点的循环双链表是否对称
#include <iostream>
#include "circledoublefun.h"
using namespace std;
/*
判断带头结点的循环双链表是否对称
循环双链表：
-------------------------------------------------
prev head next ---- prev data next ---- prev data next
-------------------------------------------------
*/
int fun(DNode *L)
{
DNode *p = L->next;
DNode *q = L->prior;
while (p != q && q->next != p)//分奇数和偶数进行判断 条件
if (p->data == q->data)//判断对称的条件
{
//p往后移动 q往前移动
p = p->next;
q = q->prior;
}
else
return 0;
return 1;
}
int main20()
{
DNode *A = cccc();
cout << fun(A) << endl;
return 0;
}
有两个循环单链表，链表头指针分别为h1,h2,试编写函数将h2链表接到h1之后,要求链接后仍保持循环链表形式
#include <iostream>
#include "circlesinglefun.h"
using namespace std;
/*
有两个循环单链表，链表头指针分别为h1,h2,试编写函数将h2链表接到h1之后,要求链接后仍保持循环链表形式
head next---data next----data next
-------------------------------
*/
void link(LNode *&h1, LNode *&h2)
{
LNode *p, *q;
p = h1, q = h2;
//p q走到循环单链表最后一个结点
while (p->next != h1)
p = p->next;
while (q->next != h2)
q = q->next;
p->next = h2;//连接
q->next = h1;//循环
}
int main21()
{
LNode *A = dddd();
LNode *B = dddd();
link(A, B);
LNode *q = A->next;
while (q != A)
{
cout << q->data << " ";
q = q->next;
}
return 0;
}
设有一个带头结点的循环单链表，其结点值为正整数设计算法反复找出链表内最小值并不断输出,并将结点从链表中删除,直到链表为空，再删除表头结点
#include <iostream>
#include "circlesinglefun.h"
using namespace std;
/*
设有一个带头结点的循环单链表，其结点值为正整数
设计算法反复找出链表内最小值并不断输出,并将结点从链表中删除,直到链表为空，再删除表头结点
L--2--4--7--1--3
L--2--4--7--3 输出1
*/
void del(LNode *&L)
{
LNode *p, *minp, *u;
while (L->next != L)
{
p = L->next;
minp = L;
while (p->next != L)//循环结束的条件
{
if (p->next->data < minp->next->data)
minp = p;
p = p->next;
}
cout << "依次输出为：";
cout << minp->next->data << endl;
u = minp->next;
minp->next = u->next;
free(u);
}
free(L);
}
int main22()
{
cout << "输入A链表：";
LNode *A = dddd();
del(A);
return 0;
}
判断单链表是否有环
#include <iostream>
#include "linklist.h"
using namespace std;
/*
判断单链表是否有环
用快慢指针法
快指针走两步 慢指针走一步 相遇就证明是有环的
*/
int findloop(LNode *L)
{
LNode *fast = L, *slow = L;
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return 1;
}
return 0;
}
int main23()
{
LNode *L = bbbb();
cout << "A:" << findloop(L);
return 0;
}
给定一个单链表L(a1,a2,a3,……,an)将其重新排列为(a1,an,a2,an-1,……)
#include <iostream>
#include "linklist.h"
using namespace std;
/*
给定一个单链表L(a1,a2,a3,……,an)将其重新排列为(a1,an,a2,an-1,……)
1 2 3 4 5
1 5 2 4 3
1 2 3 4 5 6
1 6 2 5 3 4
*/
//中点之后的结点的操作
Linklist divrev(LNode *&L)
{
//快慢指针找到链表的中点
LNode *p = L, *q = L;
while (q != NULL && q->next != NULL)//奇链表和偶链表结束的条件
{
p = p->next;
q = q->next->next;
}
LNode *L1 = new LNode;
L1->next = p->next;//新的结点连接到中点的后面的结点
p->next = NULL;//将中点后的next指向NULL
//中点之后的链表结点进行逆置操作 用头插法
LNode *p1 = L1->next, *r;
L1->next = NULL;
while (p1 != NULL)//逆置的操作
{
r = p1->next;
p1->next = L1->next;
L1->next = p1;
p1 = r;
}
return L1;
}
/*
经过上一步操作后 所得到的链表中间以后的链表是逆置的
运用奇偶链表的思想
L--1--2--3--4--5--6
L--1--2--3
L1--6--5--4
L--1--6--2--5--3--4
*/
void merge(LNode *&L)
{
LNode *r, *s;
LNode *L1 = divrev(L);
LNode *p = L->next, *q = L1->next;
L1->next = NULL;
while (q != NULL)//奇数下面的链表短 偶数一样短 就让q!=NULL满足条件
{
r = p->next;
s = q->next;
p->next = q;
q->next = r;
p = r;
q = s;
}
}
int main24()
{
LNode *L = bbbb();
merge(L);
L = L->next;
while (L != NULL)
{
cout << L->data << " ";
L = L->next;
}
return 0;
}
文章来源:https://blog.csdn.net/m0_69093426/article/details/135112948
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！