系列文章目录
速通数据结构与算法系列
1 速通数据结构与算法第一站 复杂度 http://t.csdnimg.cn/sxEGF
2 速通数据结构与算法第二站 顺序表 http://t.csdnimg.cn/WVyDb
感谢佬们支持！
目录
系列文章目录
- 前言
- 一、单链表
- 1 结构体
- 2 接口声明
- 3 打印
- 4 扩容
- 5 尾插
- 6 尾删
- 7 头插
- 8 头删
- 9 find
- 10 insert(在指定位置后一个插)
- 11 erase(删指定位置的下一个)
- 12 销毁
- 二、OJ题
- 1 删除链表元素
- 2 反转链表
- 3 合并两个有序链表
- 4 链表分割
- 5 链表的中间节点
- 6 链表的回文结构
- 7 相交链表
- 总结
前言
上一节我们学习了顺序表这一数据结构，这一节我们来学习链表，准确来说是单链表。
链表的用途十分广泛，操作系统的大部分队列都是由双链表维护的；但是单链表依旧有他的优势，
由于比双链表少了一个成员，一个节点的大小会大大减小，所以有的结构为了省内存会使用单链表
，比如哈希表会挂单链表。而且大部分的链表算法题都是以单链表为背景的，面试中问的尤为频繁
一、单链表
单链表的结构体由数据域和指针域组成
数据域用来存数据，指针域用来存下一个节点的地址
我们建3个文件，slist.h,slist.c,test.c
typedef int SLDataType;
typedef struct SListNode
{
int data;
struct SListNode* next;
}SLTNode;由于链表没什么好初始化的，所以我们在声明的接口里不用写初始化函数
还是来看一下声明的接口
接口声明
//打印
void SListPrint(SLTNode* phead);
//销毁
void SListDestroy(SLTNode** pphead);
//增加节点
SLTNode* SListBuyListNode(SLDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SLDataType x);
//尾删
void SListPopBack(SLTNode** pphead);
//头插
void SListPushFront(SLTNode** pphead, SLDataType x);
//头删
void SListPopFront(SLTNode** pphead);
//寻找
SLTNode* SListFind(SLTNode* phead, SLDataType x);
//指定位置后插
void SListInsertAfter(SLTNode** pphead, SLDataType x, SLTNode* pos);
//删指定位置的下一个
void SListEraseAfter(SLTNode** pphead, SLTNode* pos); 这个时候大家会注意到我们用的全部都是二级指针，为什么呢？
首先，我们定义的就是一个指针，所以传参传的也是指针，如果我们只传原生的指针过去
形参的修改不影响实参，我们在test.c定义的指针还是空
所以我们要传指针的地址过去，也就是二级指针
先来写一波打印
显然，打印并不会修改链表，所以我们只传一级指针就行
由于空的链表也能打印，所以我们不需要assert
void SListPrint(SLTNode* phead)
{
//由于空的链表也能打印，所以我们不用断言
//assert(phead);
SLTNode* cur = phead;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
}扩容
扩容的逻辑也相对简单，直接malloc即可
//增加节点
SLTNode* SListBuyListNode(SLDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//增加失败
if (NULL == newnode)
{
printf("malloc fail\n ");
exit(-1);
}
//增加成功
else
{
newnode->data = x;
newnode->next = NULL;
}
return newnode;
}我们先来写一个尾插
尾插
尾插的核心逻辑是先找尾，然后在让 尾->next=newnode;
当然，我们要考虑链表为空的情况由于链表为空是在预期之内的，所以我们不用断言
*pphead,但是要断言pphead
当链表为空时，newnode就是新的头
代码如下
//尾插
void SListPushBack(SLTNode** pphead, SLDataType x)
{
assert(pphead);
SLTNode* newnode = SListBuyListNode(x);
//链表为空
if (NULL == *pphead)
{
*pphead = newnode;
}
else
{
//找尾
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
//找到尾
tail->next = newnode;
}
}我们可以简单的做一波测试
SLTNode* plist = NULL;
SListPushBack(&plist, 3);
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 4);
SListPrint(plist);
（确实挺不错的）
尾删
显然，我们不能删空链表，所以需要断言*pphead
尾删要分两种情况：只有一个节点和不只有一个节点
当只有一个节点时，我们就不用找尾了，直接删
而不止一个节点时要先找尾
代码如下
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
//尾删不能为空
assert(*pphead);
//只有一个节点
if (((*pphead)->next) == NULL)
{
free(*pphead);
*pphead = NULL;
}
SLTNode* tail = *pphead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}我们再做一波测试
SLTNode* plist = NULL;
SListPushBack(&plist, 3);
SListPushBack(&plist, 1);
SListPushBack(&plist, 6);
SListPopBack(&plist);
SListPrint(plist);
printf("\n");
SListPushBack(&plist, 2);
SListPushBack(&plist, 4);
SListPopBack(&plist);
SListPrint(plist);
由此可见，尾插尾删由于要找尾，时间复杂度都是O（n）
这个时候有人要问了：尾插尾删并不改变头指针啊，也就是说只传一级指针也没问题
但如果刚开始链表为空调用尾插和只有一个节点时尾删显然就需要修改了，所以我们依然需要传二级指针
头插
头插就简单多了，给大家画一张图就够了
-》
代码很简单
//头插
void SListPushFront(SLTNode** pphead, SLDataType x)
{
assert(pphead);
SLTNode* newnode = SListBuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}头删
头删的逻辑一样简单，我们只需提前保存当前头的下一个，再删头即可
//头删
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
//提前保存头节点的下一个
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = NULL;
*pphead = next;
}我们简单的测试一下
SLTNode* plist = NULL;
SListPushFront(&plist, 6);
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPopFront(&plist);
SListPrint(plist);
由原理可知：链表的头插和头删都是高贵的O（1），这也就是为什么STL的slist选择提供
push_front()和pop_front()而非push_back()和pop_back()的原因
寻找
寻找返回的是某值所在节点的指针
由于同样不修改链表，所以我们传一级指针
代码如下
/寻找
SLTNode* SListFind(SLTNode* phead, SLDataType x)
{
SLTNode* cur = phead;
while (cur->next)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
//没找见
return NULL;
}
我们再来实现一下insert
我们实现的时特定位置后插，大体逻辑是这样的
//指定位置后插
void SListInsertAfter(SLTNode** pphead, SLDataType x, SLTNode* pos)
{
assert(pphead);
//断言pos
assert(pos);
SLTNode* newnode = SListBuyListNode(x);
//处理链接关系
newnode->next = pos->next;
pos->next = newnode;
}再来搞一下erase
erase的逻辑大同小异，我们只需提前保存下一个，改一下链接即可
但是要注意的是由于要删pos的下一个位置，删的这个位置不能为空
//删指定位置的下一个
void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
//断言pos
assert(pos);
//删的时候下一个位置不能是空
assert(pos->next);
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}我们再测试一波
SLTNode* plist = NULL;
SListPushFront(&plist, 6);
SListPushBack(&plist, 4);
SListPushBack(&plist, 4);
SListPushBack(&plist, 2);
SListPushBack(&plist, 4);
SLTNode* pos = SListFind(plist, 2);
SListInsertAfter(&plist, 7, pos);
SListPrint(plist);
printf("\n");
SListEraseAfter(&plist, pos);
SListPrint(plist);
SListDestroy(&plist);
最后我们要来写一下销毁
销毁
销毁的逻辑在于你每次都有保存要销毁节点的下一个，然后再销毁当前节点，最后再给头指针置空
//销毁
void SListDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
//提前存好下一个
SLTNode* next = cur->next;
free(cur);
cur = next;
}
//销毁头指针
*pphead = NULL;
}二、OJ题
我们来挑一些比较经典、面试中会常常问到的相对简单的题目来做。
1 删除链表元素
题目链接： . - 力扣（LeetCode）
这道题有两种方法，我们可以就在链表内部删，也可以取不等于val的尾插至新链表
法一：
删除的逻辑非常简单，就是我们实现单链表的中间删逻辑，定义一前一后两个指针
只需考虑一下头删的情况即可
struct ListNode* removeElements(struct ListNode* head, int val)
{
if (head == NULL)
{
return NULL;
}
struct ListNode* Node = head;
struct ListNode* prev;
while (Node)
{
if (Node->val == val)
{
if (Node == head)//ͷɾ
{
head = head->next;
}
else
{
prev->next = Node->next;
free(Node);
Node = prev->next;
}
}
else
{
prev = Node;
Node = Node->next;
}
}
return head;
}
法二：
尾插的逻辑也简单，这个时候有个技巧，为了避免每次尾插时都要找尾，我们直接定义一个尾指针每次记录一下即可
简单是简单，但是如果仅考虑到这样写完代码后提交就直接报错了
struct ListNode* removeElements(struct ListNode* head, int X)
{
if (head == NULL)
{
return NULL;
}
struct ListNode* newhead = NULL, * tail = NULL;
struct ListNode* cur = head;
while (cur)
{
if (cur->val != X)
{
if (tail == NULL)
{
newhead = tail = cur;
}
else
{
tail->next = cur;
tail = cur;
// tail->next=NULL;
}
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
return newhead;
}如果原链表最后一个元素是要删的那个而前一个不是，当我们删了后一个之后，后一个的next就变成了野指针
如图所示
所以我们需要置空尾指针，也就是在最后
tail=tail->next;此时你再提交，发现依然编不过，此时你会发现这个用例叫【7，7，7，7】 val=7；
由于每个元素都要被删，所以尾指针根本就是空的，不能解引用
所以我们要这样
if (tail)
tail->next = NULL;最后的代码是这样的
struct ListNode* removeElements(struct ListNode* head, int X)
{
if (head == NULL)
{
return NULL;
}
struct ListNode* newhead = NULL, * tail = NULL;
struct ListNode* cur = head;
while (cur)
{
if (cur->val != X)
{
if (tail == NULL)
{
newhead = tail = cur;
}
else
{
tail->next = cur;
tail = cur;
// tail->next=NULL;
}
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
if (tail)
tail->next = NULL;
return newhead;
}（最后终于过了）
2 反转链表
题目链接：. - 力扣（LeetCode）
这个题我们可以有两个思路：1遍历链表，改指针指向
显然，双指针是不够的，如图
如果我们改了1到2的指向，那3这个节点就找不到了，所以我们需要三指针
以prev和cur改指向，以next记录下一个节点的位置
最后改完指向时，next为空，我们返回的是cur
所以由于最后一步next可能为空，所以我们每次迭代next前，都要判空
代码如下
ListNode* reverseList(ListNode* head)
{
if (head == nullptr)
return nullptr;
ListNode* prev = nullptr;
ListNode* cur = head;
ListNode* next = cur->next;
while (cur)
{
cur->next = prev;
prev = cur;
cur = next;
if (next)
next = next->next;
}
return prev;
}也可以有第二种思路
2 遍历原链表，依次头插至新链表
代码如下，也是非常简单
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL)
{
return NULL;
}
struct ListNode* newhead = NULL;
//ͷ嵽newhead
struct ListNode* cur = head;
while (cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
//
cur = next;
}
return newhead;
}
3 合并两个有序链表
题目链接：. - 力扣（LeetCode）
相较于合并两个有序数组，合并两个有序链表就简单多了，我们可以直接找小的尾插
每次标记一下尾指针，尾插的题做起来还是很舒服的。
仅仅考虑一下头为空的情况即可
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode* cur1 = list1;
struct ListNode* cur2 = list2;
struct ListNode* head=NULL, * tail = NULL;
while (cur1 && cur2)
{
if (cur1->val <= cur2->val)
{
if (head == NULL)
{
head = tail = cur1;
}
else
{
tail->next = cur1;
tail = tail->next;
}
cur1 = cur1->next;
}
else
{
if (head == NULL)
{
head = tail = cur2;
}
else
{
tail->next = cur2;
tail = tail->next;
}
cur2 = cur2->next;
}
}
//cur1先结束了
if (cur1 == NULL)
{
tail->next = cur2;
}
//cur2先结束了
if (cur2 == NULL)
{
tail->next = cur1;
}
return head;
}还可以用带哨兵位的做法
带了哨兵位的好处就是，我们不用考虑头为空的事情了
虽然力扣不会检测内存泄漏，但我们最好还是free一下我们的头节点
记得临时保存一下，要不然就找不到链表的头啦
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if (list1 == NULL)
{
return list2;
}
if (list2 == NULL)
{
return list1;
}
struct ListNode* cur1 = list1;
struct ListNode* cur2 = list2;
struct ListNode* guard = NULL, * tail = NULL;
guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next = NULL;
while (cur1 && cur2)
{
if (cur1->val < cur2->val)
{
tail->next = cur1;
tail = tail->next;
cur1 = cur1->next;
}
else
{
tail->next = cur2;
tail = tail->next;
cur2 = cur2->next;
}
}
//cur1先结束了
if (cur1 == NULL)
{
tail->next = cur2;
}
//cur2先结束了
if (cur2 == NULL)
{
tail->next = cur1;
}
struct ListNode* head = guard->next;
free(guard);
return head;
}4 链表分割
链表分割_牛客题霸_牛客网
显然，在一个链表上操作较为麻烦，我们可以开两个链表，将小于x的节点插到一个链表中
将大于x的节点插入另一个链表中，再将两个链表穿起来，返回小链表的头即可
注意：将大链表的头接入小链表的尾时，记得给大链表的尾置空。
代码如下~
ListNode* partition(ListNode* pHead, int x)
{
struct ListNode* LessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* GreaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));
//遍历链表
ListNode* cur = pHead;
ListNode* tail1 = LessHead;
ListNode* tail2 = GreaterHead;
while (cur)
{
if (cur->val < x)
{
//小于x就尾插至Less链表
tail1->next = cur;
tail1 = cur;
}
else
{
//否则就尾插至Greater链表
tail2->next = cur;
tail2 = cur;
}
cur = cur->next;
}
//链接两个链表
tail1->next = GreaterHead->next;
tail2->next = nullptr;
//保存下要返回的节点
struct ListNode* tmp = LessHead->next;
free(LessHead);
free(GreaterHead);
return tmp;
}5 链表的中间节点
题目链接 ：. - 力扣（LeetCode）
这个题就简单了，我们可以用快慢指针来做，快指针一次走两步，慢指针一次走一步
当链表长度为奇数时，最后fast->next为空,链表只有一个中间节点
当链表长度为偶数时，最后fast为空,我们的slow将会是两个中间节点的第二个
代码如下
struct ListNode* middleNode(struct ListNode* head)
{
//ָ
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
6 链表的回文结构
题目链接 . - 力扣（LeetCode）
在前面的铺垫之后，回文链表的思路就简单了，我们先找到链表的中间节点，然后从中间断开
逆置后半段，然后让两个指针遍历，如果有不相同的节点，就不是回文链表。我们可以CV一下之前的中间节点和逆置。
代码如下
class Solution {
public:
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL)
{
return NULL;
}
struct ListNode* newhead = NULL;
//ͷ嵽newhead
struct ListNode* cur = head;
while (cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
//
cur = next;
}
return newhead;
}
ListNode* middleNode(struct ListNode* head)
{
//快慢指针
ListNode*fast=head;
ListNode*slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
bool isPalindrome(ListNode* head)
{
ListNode*middle=middleNode(head);
ListNode*rmiddle=reverseList(middle);
while(rmiddle!=nullptr)
{
if(rmiddle->val!=head->val)
{
return false;
}
rmiddle=rmiddle->next;
head=head->next;
}
return true;
}
};7 相交链表
题目链接 ：. - 力扣（LeetCode）
显然，两个链表如果相交，那他们的最后一个节点一定相同。
我们可以先遍历一遍两个链表，求出各自的长度，顺便判断一下最后一个节点是否相同，不相同也是直接返回NULL
然后让长的链表先走差距步，再让两个指针一起走，直到遇到相同的节点
值得注意的是，这里两个链表的长度最小为1，所以我们在判断时不能用slow->next和fast->next；而应用slow和fast
代码如下
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
int lenA = 1;
int lenB = 1;
struct ListNode* tailA = headA;
struct ListNode* tailB = headB;
while (tailA)
{
lenA++;
tailA = tailA->next;
}
while (tailB)
{
lenB++;
tailB = tailB->next;
}
//如果相交，尾节点一定相同 //这个条件很有必要
if (tailA != tailB)
{
return NULL;
}
//快的先走差距步，再一起走
struct ListNode* fast = lenA > lenB ? headA : headB;
struct ListNode* slow = lenA > lenB ? headB : headA;
int gap = abs(lenA - lenB);
while (gap--)
{
fast = fast->next;
}
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}总结
做总结，单链表由于"不能倒着走"的特性使其在运用上多有限制，这也就是为什么OJ题中的背景
都是单链表，所以在C++11中STL更新了单链表slist用的人也不多。
下篇博客我们将学习双链表，将会轻松很多，但是会接触三个不那么轻松的OJ题。
水平有限，还请各位大佬指正。如果觉得对你有帮助的话，还请三连关注一波。希望大家都能拿到心仪的offer哦。
