深圳建站公司设计_免备案虚拟主机空间_机构类网站有哪些_企业网络营销顾问

3.链表

3.1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

链表的物理结构

1.从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

3.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

2. 带头或者不带头

head 哨兵位，不存储有效数据

3. 循环或者非循环
   

共有8种

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

3.3 无头+单向+非循环链表增删查改接口实现

typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* phead);
// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pphead);
// 单链表头删
void SListPopFront(SListNode** pphead);
// 单链表查找
SListNode* SListFind(SListNode* phead, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);

3.3.1 动态申请一个节点

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("BuySListNode::mallo fail!");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}

3.3.2 单链表打印

void SListPrint(SListNode* phead)
{SListNode *cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

3.3.3 单链表尾插

思路

void SListPushBack(SListNode** pphead, SLTDateType x)
{SListNode* newnode = BuySListNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾SListNode* tail =*pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

3.3.4 单链表的头插

思路比较简单

void SListPushFront(SListNode** pphead, SLTDateType x)
{SListNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}

3.3.5 单链表的尾删

思路

void SListPopBack(SListNode** pphead)
{assert(*pphead);// 1、只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{// 2、多个节点//找尾SListNode* prev = NULL;SListNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

3.3.6 单链表头删

思路

void SListPopFront(SListNode** pphead)
{assert(*pphead);SListNode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}

3.3.7 单链表查找

思路比较简单，如果找到就返回找到的结点，没找到就返回NULL

SListNode* SListFind(SListNode* phead, SLTDateType x)
{SListNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

3.3.8 单链表在pos位置之后插入x

思路,比较简单。

void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

3.3.9 单链表删除pos位置之后的值

void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos->next);SListNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

3.4 链表面试题

1. 删除链表中等于给定值 val 的所有节点。

删除节点链接

2. 反转一个单链表。

反转一个单链表

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

返回中间结点

4. 输入一个链表，输出该链表中倒数第k个结点。

返回倒数第K个节点

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

合并两个有序链表

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

链表分割

7. 链表的回文结构。

8. 输入两个链表，找出它们的第一个公共结点。

9. 给定一个链表，判断链表中是否有环。

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

11. 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝。

12. 其他 。

力扣链表OJ链接+牛客链表OJ链接