数据结构-链表

简介

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

特点

链表的一个节点通常有两个元素：数据域和指针域

1. 数据域：存放数据
2. 指针域：存放下一个节点的地址

类型

1. 单向链表：通常有个头节点，不存放实际的值，它含有一个指针，指向存放元素的第一个节点
2. 循环链表：特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环
3. 双向链表：每个结点除含有数据域外，还有两个指针域，分别指向直接前驱结点和直接后继结点

并且链表按是否有头节点分为：

1. 带头结点的链表：头结点一般称为head，且其数据域data不存放任何内容，而指针域next指向第一个数据域有内容的结点(一般把这一个结点叫做第一个结点);
2. 不带头结点的链表

链表的声明

struct ListNode{
    double value;
    ListNode *next;
    ListNode(double valuel, ListNode *nextl = nullptr)//构造函数
    {
        value = value1;
        next = next1;
    }
};
ListNode *head = nullptr;	//头节点

例题

反转链表

合并两个有序链表

两个链表的第一个公共节点

链表中环的入口节点