文章目录
一、单链表的逆置（两种方法）
1.无限头插法（简单）
这里所写代码都是带头结点的
首先我们来演示什么是无限头插法
1）首先断开头结点，并设立两个指针，指针p和指针q,指针p指向plist->next,
指针q指向p->next,（这里的思路可以参照之前写过的单链表销毁2）
2）将头节点后面的节点依次头插到头结点后面，具体步骤看下图演示
以此类推，就可以将链表完全逆置了
其次我们进行代码的实现
单链表基本操作
#include<stdio.h>
#include <cassert>
#include <stdlib.h>
typedef int ELEM_TYPE;
typedef struct Node {
ELEM_TYPE data;//数据域（保存数据的有效值）
struct Node* next;//指针域（保存下一个有效结点的地址）
}Node,*PNode;
//初始化
void Init_list(struct Node* plist) {
assert(plist !=NULL);
plist->next = NULL;
}
//按位置插
bool Insert_pos(PNode plist, int pos, ELEM_TYPE val) {
assert(plist != NULL);
//assert(pos >= 0 && pos <=Getlength(plist));
struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
pnewnode->data = val;
struct Node* p = plist;
for (int i = 0; i < pos; i++) {
p = p->next;
}
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
//打印
void Show(PNode plist) {
assert(plist != NULL);
struct Node* p = plist->next;
for (; p != NULL; p = p->next) {
printf("%d ",p->data);
}
printf("\n");
}
核心代码
//方法一，无限头插 如果需要逆置，至少需要存在两个节点
void Resver1(struct Node* plist) {
assert(plist != NULL);
int length = Getlength(plist);
if (length < 2) {
return;
}
//1.申请两个指针p和q 分别指向第一个有效节点和第二个有效节点
struct Node* p = plist->next;
struct Node* q = p->next;
//2.断开头结点
plist->next = NULL;
//通过p和q的搭配，将所有节点依次头插进来
while (p!=NULL) {
q=p->next;
p->next = plist->next;
plist->next = p;
p = q;
}
}
测试代码
int main(){
struct Node head;
Init_list(&head);
for (int i = 0; i <10; i++) {
Insert_pos(&head, i, i + 1);
}
Show(&head);
Resver1(&head);
Show(&head);
}
运行结果
2.利用三个指针（较难）
图示法演示具体操作
这个方法较上一个方法有些难度
1）设置三个指针，并断开头结点，将p设置为空
2）q的指针域保存p的地址，从而将箭头反转
3）p=q; q=r; 从而实现指针的反复利用
4）将头结点插入到p节点后面
思考：这个循环截至条件是什么？ 答：我们知道在p节点之后还要插入头结点，所以p指针是不能指向空的，此时只有当q为空时，循环才会结束
代码实现
单链表具体操作
#include<stdio.h>
#include <cassert>
#include <stdlib.h>
typedef int ELEM_TYPE;
typedef struct Node {
ELEM_TYPE data;//数据域（保存数据的有效值）
struct Node* next;//指针域（保存下一个有效结点的地址）
}Node,*PNode;
//初始化
void Init_list(struct Node* plist) {
assert(plist !=NULL);
plist->next = NULL;
}
//按位置插
bool Insert_pos(PNode plist, int pos, ELEM_TYPE val) {
assert(plist != NULL);
//assert(pos >= 0 && pos <=Getlength(plist));
struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
pnewnode->data = val;
struct Node* p = plist;
for (int i = 0; i < pos; i++) {
p = p->next;
}
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
//打印
void Show(PNode plist) {
assert(plist != NULL);
struct Node* p = plist->next;
for (; p != NULL; p = p->next) {
printf("%d ",p->data);
}
printf("\n");
}
核心代码
//第二种方法 三个指针
void Reserve2(PNode plist) {
assert(plist != NULL);
int length = Getlength(plist);
if (length < 2) {
return;
}
struct Node* p = plist->next;
struct Node* q = p->next;
struct Node* r ;
p->next = NULL; //第一步操作
while (q != NULL) {
r=q->next;
q->next = p; //第二步操作
p = q; //第三步操作
q = r;
}
plist->next = p; //第四步操作
}
测试代码
int main(){
struct Node head;
Init_list(&head);
for (int i = 0; i <10; i++) {
Insert_pos(&head, i, i + 1);
}
Show(&head);
Resver1(&head);
Show(&head);
Reserve2(&head);
Show(&head);
}
测试结果
二、如何判断两个链表是否存在交点，如果存在，则返回第一个相交点（中等难度）
1）这道题的思路是：尾结点相同，即两个单链表相交，所以我们需要定义两个指针p和q分别指向单链表头结点的下一个节点，然后遍历到最后一个节点。
2）但是我们又该如何判断相交点在哪里呢？我们这里要注意到一个问题是两个单链表的长度有可能不相同，所以我们应该将长度较长的单链表先进行遍历，遍历的长度为他们之间链表长度的差值，然后同时向后遍历，直到两个节点相同
由于这道题思路较为简单，于是我们直接进行代码的实现
单链表基本操作
#include<stdio.h>
#include <cassert>
#include <stdlib.h>
typedef int ELEM_TYPE;
typedef struct Node {
ELEM_TYPE data;//数据域（保存数据的有效值）
struct Node* next;//指针域（保存下一个有效结点的地址）
}Node,*PNode;
//初始化
void Init_list(struct Node* plist) {
assert(plist !=NULL);
plist->next = NULL;
}
//按位置插
bool Insert_pos(PNode plist, int pos, ELEM_TYPE val) {
assert(plist != NULL);
//assert(pos >= 0 && pos <=Getlength(plist));
struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
pnewnode->data = val;
struct Node* p = plist;
for (int i = 0; i < pos; i++) {
p = p->next;
}
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
//打印
void Show(PNode plist) {
assert(plist != NULL);
struct Node* p = plist->next;
for (; p != NULL; p = p->next) {
printf("%d ",p->data);
}
printf("\n");
}
核心代码
struct Node* Intersection(struct Node *plist1,struct Node* plist2) {
//0.安全性处理
assert(plist1 != NULL&&plist2!=NULL);
//1.定义两个指针，让它们分别走到到最后的节点处，判断是否相交
struct Node* p = plist1->next;
struct Node* q = plist2->next;
for (; p != NULL; p = p->next);
for (; q != NULL; q = q->next);
if (p== q) {
printf("存在交点\n");
}
//3，找到相交点
int len1 = Getlength(plist1);
int len2 = Getlength(plist2);
struct Node* m = (len1 > len2) ? plist1 : plist2;//将较为长的单链表给plist1
struct Node* n = (len1 > len2) ? plist2 : plist1;//将较为短的链表给plist2
//4.让两链表起始长度相同，abs库函数，意思为：|len1-len2|
for (int i = 0; i < abs(len1-len2); i++) {
m = m->next;
}
//5.找到相交点
while (m != n) {
m = m->next;
n = n->next;
}
return m;
}
测试代码
int main(){
struct Node head1, head2;
Init_list(&head1);
for (int i = 0; i < 10; i++) {
Insert_pos(&head1, i, i + 1);
}
Show(&head1);
Init_list(&head2);
for (int i = 0; i <=15; i++) {
Insert_pos(&head2, i,i+11);
}
Show(&head2);
//将两个单链表手动相交
struct Node* p = &head2;
for (int i = 0; i < 12; i++) {
p = p->next;
}
struct Node* q = &head1;
for (int i = 0; i < 7; i++) {
q = q->next;
}
p->next = q->next;
Show(&head1);
Show(&head2);
struct Node* tem= Intersection(&head1, &head2);
printf("%d", tem->data);
}
运行结果
三、判断一个单链表是否存在环，如果存在环，则找到如环点（较难）
画图演示
那我们如何发现此单链表存在环呢？根据快慢指针，我们知道，如果存在环，则当快慢指针都进入环的时候，一定会在环内相遇，而当不存在环的时候，快指针在遇到NULL时，直接退出，循环结束就可以了
由上图可知：我们最终的得出结论，让相遇处的结点与起始点的结点同时出发，这样当两节点相同时，便是入口处的节点
代码实现
单链表基本操作
#include<stdio.h>
#include <cassert>
#include <stdlib.h>
typedef int ELEM_TYPE;
typedef struct Node {
ELEM_TYPE data;//数据域（保存数据的有效值）
struct Node* next;//指针域（保存下一个有效结点的地址）
}Node,*PNode;
//初始化
void Init_list(struct Node* plist) {
assert(plist !=NULL);
plist->next = NULL;
}
//按位置插
bool Insert_pos(PNode plist, int pos, ELEM_TYPE val) {
assert(plist != NULL);
//assert(pos >= 0 && pos <=Getlength(plist));
struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
pnewnode->data = val;
struct Node* p = plist;
for (int i = 0; i < pos; i++) {
p = p->next;
}
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
//判空
bool IsEmpty(PNode plist) {
if (plist->next == NULL) {
return true;
}
return false;
}
核心代码
struct Node* Ring(struct Node* plist) {
//.安全性处理
assert(plist != NULL);
if (IsEmpty(plist)) {
return NULL;
}
//1.定义两个快慢指针，快指针一次走两步，慢指针一次走一步
struct Node* fast = plist;
struct Node* slow = plist;
slow = slow->next;
fast = fast->next;
if (fast != NULL) { //进行安全性处理
fast = fast->next;
}
//2.同步向后走
while (fast != slow && fast != NULL) {
slow = slow->next;
fast = fast->next;
if (fast != NULL) { //进行安全性处理
fast = fast->next;
}
}
if (fast == NULL) {
return NULL;
}
else {
printf("存在入环点\n");
}
//如果if没有进去，则代表有环，找到入环点
struct Node* p = plist;
while (fast != p) {
fast = fast->next;
p = p->next;
}
return p;
}
测试代码
int main(){
//1.插入数据
struct Node head;
Init_list(&head);
for (int i = 0; i < 10; i++) {
Insert_pos(&head, i, i + 1);
}
//2.手动给单链表设置一个入环点
struct Node* q = &head;
for (int i = 0; i < 10; i++) {
q = q->next;
}
struct Node* p = &head;
for (int i = 0; i < 6; i++) {
p = p->next;
}
q->next = p;
//3.测试入环点的数据
struct Node* tem = Ring(&head);
printf("%d", tem->data);
四、单链表给一个随机节点的地址，如何在o(1)时间内删除这个节点（不能是尾结点）（简单）
思路：我们知道了这个节点的地址，但是由于是单链表，我们不清楚头结点在哪里，因此我们始终无法找到当前待删除节点的上一个节点，所以我们只能进行替换的方法，就是将待删除节点的下一个节点的数据域给到待删除节点，然后删除待删除节点的下一个节点
核心代码
bool Del_Node(struct Node* del_node) {
assert(del_node != NULL);
//狸猫换太子
if (del_node->next == NULL) {//狸猫得存在
return false;
}
del_node->data = del_node->next->data; //将狸猫化妆为太子
struct Node* p = del_node->next; //让p指向狸猫
del_node->next = p->next; //跨越指向
free(p); //释放待删除节点
return true;
}