【数据结构与算法篇】单链表及相关OJ算法题
🥕个人主页：开敲🍉
🔥所属专栏：数据结构与算法🍅
🌼文章目录🌼
1. 单链表的实现(近300行实现代码)
1.1 SList.h 头文件的声明
1.2 SList.c 源文件的定义
1.3 Test.c 源文件的测试
2. OJ算法题
2.1 206. 反转链表 - 力扣（LeetCode）
2.2 203. 移除链表元素 - 力扣（LeetCode）
2.3 876. 链表的中间结点 - 力扣（LeetCode）
1. 单链表的实现(近300行实现代码)
1.1 SList.h 头文件的声明
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct SListNode SL;
struct SListNode
{
SLDataType value;
SL* next;
};
//打印
void SLPrint(SL* phead);x
//申请空间
SL* SLBuyNode(SLDataType x);
//尾插
void SLPushBack(SL** pphead, SLDataType x);
//头插
void SLPushHead(SL** pphead, SLDataType x);//指定插入
void SLPushDesi(SL** pphead,int y,SLDataType x);
//尾删
void SLPopBack(SL** pphead);
//头删
void SLPopHead(SL** pphead);//指定删除
void SLPopDesi(SL** pphead, int y);
//查找
void SLFind(SL* pphead, int y);//更改
void SLChange(SL** pphead, int y, SLDataType x);
1.2 SList.c 源文件的定义
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"//打印
void SLPrint(SL* phead)
{
SL* pcur = phead;
while(pcur)
{
printf("%d->", pcur->value);
pcur = pcur->next;
}
printf("NULL\n");
}
//申请空间
SL* SLBuyNode(SLDataType x)
{
SL* pcur = (SL*)malloc(sizeof(SL));
if (pcur == NULL)
{
perror("maolloc");
exit(-1);
}
pcur->value = x;
pcur->next = NULL;
return pcur;
}//尾插
void SLPushBack(SL** pphead, SLDataType x)
{
SL* find = SLBuyNode(x);
SL* pcur = *pphead;
if ((*pphead) == NULL)
{
*pphead = find;
}
else
{
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = find;
}
}//头插
void SLPushHead(SL** pphead, SLDataType x)
{
SL* find = SLBuyNode(x);
if ((*pphead) == NULL)
{
*pphead = find;
}
else
{
find->next = *pphead;
*pphead = find;
}
}//寻找
SL* FindSList(SL* pf, int y)
{
SL* pcur = pf;
while (y - 2)
{
if (pcur == NULL)
{
return NULL;
}
pcur = pcur->next;
y--;
}
return pcur;
}
//指定插入
void SLPushDesi(SL** pphead, int y , SLDataType x)
{
assert(*pphead&&pphead);
SL* pcur = FindSList(*pphead, y);
if (!pcur)
{
printf("插入越界，无法在此处插入数据!\n");
exit(-1);
}
SL* ptmp = SLBuyNode(x);
ptmp->next = pcur->next;
pcur->next = ptmp;
}//尾删
void SLPopBack(SL** pphead)
{
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
return;
}
SL* pcur = *pphead;
SL* ptmp = *pphead;
while (pcur->next)
{
pcur = pcur->next;
while (ptmp->next->next)
{
ptmp = ptmp->next;
}
}
ptmp->next = NULL;
free(pcur);
}
//头删
void SLPopHead(SL** pphead)
{
assert(pphead&&*pphead);
SL* pcur = *pphead;
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
return;
}
(*pphead) = (*pphead)->next;
free(pcur);
}//指定删除
void SLPopDesi(SL** pphead, int y)
{
assert(pphead&&*pphead);
SL* pcur = FindSList(*pphead, y);
SL* ptmp = pcur->next;
if (!(pcur->next))
{
printf("删除越界，无法在此处删除数据!\n");
return;
}
pcur->next = pcur->next->next;
free(ptmp);
}
//查找
void SLFind(SL* pphead, int y)
{
assert(pphead);
SL* pcur = FindSList(pphead, y);
if (!(pcur->next))
{
printf("查询失败!\n");
return;
}
printf("查询成功!\n");
printf("该位置数据为:%d\n", pcur->next->value);
return;
}
//更改
void SLChange(SL** pphead, int y, SLDataType x)
{
assert(*pphead);
SL* pcur = FindSList(*pphead, y);
if (!(pcur->next))
{
printf("更改失败,该位置无数据可更改!\n");
return;
}
pcur->next->value = x;
}
1.3 Test.c 源文件的测试
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void TestSList()
{
SL* plist = NULL;//尾插
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLPrint(plist);//打印//头插
SLPushHead(&plist, 0);
SLPrint(plist);//打印//指定插入
SLPushDesi(&plist, 3, 5);
SLPrint(plist);//越界指定插入
SLPushDesi(&plist, 7, 10);
SLPrint(plist);//尾删
SLPopBack(&plist);
SLPrint(plist);//头删
SLPopHead(&plist);
SLPrint(plist);//指定删除
SLPopDesi(&plist, 3);
SLPrint(plist);//指定删除越界
SLPopDesi(&plist, 5);
//查找SLFind(plist, 4);
//查找越界
SLFind(plist, 5);
//更改
SLChange(&plist, 3, 1);
SLPrint(plist);
//更改越界
SLChange(&plist, 5, 1);
}
int main()
{
TestSList();
return 0;
}
2. OJ算法题
2.1 206. 反转链表 - 力扣（LeetCode）
//思路：三指针解法。指针pf1开始指向NULL，指针pf2开始指向头节点，指针pf3指向pf2中的next节点，三个同时往后遍历，当pf2走到NULL时，pf1就是要返回的头节点
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* pf1 = NULL;
struct ListNode* pf2 = head;
while(pf2)
{
struct ListNode* pf3 = pf2->next;
pf2->next = pf1;
pf1 = pf2;
pf2 = pf3;
}
return pf1;
}
2.2 203. 移除链表元素 - 力扣（LeetCode）
//思路：遍历。使用指针pf1放头节点，遍历链表，如果pf1->->val等于题目所给val，则直接将当前next指向next->next，跳过val所在节点
//需要注意的是，需要考虑链表中的val都是题目所给val已经空链表的情况
struct ListNode* removeElements(struct ListNode* head, int val)
{
while(head!=NULL&&(head->val)==val)
{
head = head->next;
}
if(!head)
{
return head;
}
struct ListNode* pf1 = head;
while(pf1->next)
{
if((pf1->next->val)==val)
{
pf1->next = pf1->next->next;
}
else
{
pf1 = pf1->next;
}
}
return head;
}
2.3 876. 链表的中间结点 - 力扣（LeetCode）
//思路：快慢指针算法，这种寻找中间点的算法题使用快慢指针会非常便捷高效。主要思路就是指针pf1每次走一个节点，指针pf2每次走两个节点，当pf2走到末节点或走出链表时，pf1所指向的就是需要返回的中间节点。
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* pf1 = head;
struct ListNode* pf2 = head;
while(pf2&&pf2->next)
{
pf2 = pf2->next->next;
pf1 = pf1->next;
}
return pf1;
}
