文章目录
一、单链表简述
二、单链表
三、单链表的应用
1、判断两个单链表是否相交并返回第一个交点
2、判断单链表是否有环
3、在O(1)下删除一个结点p
4、在O(1)下添加一个结点在结点p前面
5、逆置单链表

一、单链表简述
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素+ 指针，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
1、单链表的定义

链表是通过一组地址任意的存储单元来存储线性表中的数据元素，这些存储单元可以是连续的，也可以是不连续的。
2、单链表的特点

逻辑相邻的数据元素其物理存储位置不一定相邻。为表示数据元素之间的线性关系，在存储数据元素时，除了要存放数据元素自身的信息外，还要额外存放一个其直接后继的存储地址。
3、图解单链表


二、单链表
#pragma once

typedef int ElemType;

typedef struct Node
{
	union
	{
		int length;
		ElemType data;
	};

	struct Node *next;
}LNode, *LinkList;

void InitLinkList(LinkList list);

int InsertLinkListPos(LinkList list, ElemType val, int pos);
int InsertLinkListHead(LinkList list, ElemType val);
int InsertLinkListTail(LinkList list, ElemType val);

void ShowLinkList(LinkList list);

int DeleteLinkListPos(LinkList list, int pos);
int DeleteLinkListHead(LinkList list);
int DeleteLinkListTail(LinkList list);

void ClearLinkList(LinkList list);
void DestoryLinkList(LinkList list);

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include "List.h"

//判断链表是否为空
static void DeterPointIsNULL(LinkList list)
{
	assert(list != NULL);
	if (list == NULL)
	{
		printf("list is NULL, Please Check\n");
		exit(0);
	}
}

//申请一个新节点
static LinkList _ApplyNode(ElemType val, LinkList point)
{
	LinkList s = (LinkList)malloc(sizeof(LNode));
	assert(s != NULL);

	s->data = val;
	s->next = point;

	return s;
}

//初始化一个单链表
void InitLinkList(LinkList list)
{
	DeterPointIsNULL(list);

	list->length = 0;
	list->next = NULL;
}

//插入
int InsertLinkListPos(LinkList list, ElemType val, int pos)
{
	DeterPointIsNULL(list);

	if (pos < 0 || pos > list->length)
	{
		printf("pos is out of range, Insert fail\n");
		return 0;
	}

	LinkList p = list;

	while (pos > 0)
	{
		p = p->next;
		pos--;
	}

	p->next = _ApplyNode(val, p->next);

	return 1;
}

int InsertLinkListHead(LinkList list, ElemType val)
{
	return InsertLinkListPos(list, val, 0);
}

int InsertLinkListTail(LinkList list, ElemType val)
{
	DeterPointIsNULL(list);

	return InsertLinkListPos(list, val, list->length);
}

//打印
void ShowLinkList(LinkList list)
{
	DeterPointIsNULL(list);

	LinkList p = list->next;

	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

//删除
int DeleteLinkListPos(LinkList list, int pos)
{
	DeterPointIsNULL(list);

	if (pos < 0 || pos >= list->length)
	{
		printf("pos is out of range, Insert fail\n");
		return 0;
	}

	LinkList p = list;

	while (pos > 0)
	{
		p = p->next;
		pos--;
	}

	LinkList q = p->next;
	p->next = q->next;
	free(q);

	list->length--;

	return 1;
}
int DeleteLinkListHead(LinkList list)
{
	return DeleteLinkListPos(list, 0);
}

int DeleteLinkListTail(LinkList list)
{
	DeterPointIsNULL(list);

	return DeleteLinkListPos(list, list->length - 1);
}

//清空和销毁
void ClearLinkList(LinkList list)
{
	DestoryLinkList(list);
}

void DestoryLinkList(LinkList list)
{
	DeterPointIsNULL(list);

	while (list->next != NULL)
	{
		DeleteLinkListHead(list);
	}
}

三、单链表的应用
1、判断两个单链表是否相交并返回第一个交点
解析：按照单链表的构成来说，两个单链表相交的条件是两个单链表中有一个结点数据元素相等，存储的下一个元素地址相同，如下图所示：


可以发现，当两个单链表相交时，其后面的结点也一定相等，即可以转化为当两个单链表剩余结点数相等时，同时向后进行移动，相等的结点即为两个单链表第一个相交的结点。
代码：
//相交并返回第一个交点
LinkList IntersectLinkList(LinkList list1, LinkList list2)
{
	DeterPointIsNULL(list1);
	DeterPointIsNULL(list2);

	int len1 = list1->length;
	int len2 = list2->length;

	LinkList p = list1;
	LinkList q = list2;

	if (len1 > len2)
	{
		for (int i = 0; i < len1; ++i)
		{
			p = p->next;
		}
	}
	if (len1 < len2)
	{
		for (int i = 0; i < len2; ++i)
		{
			q = q->next;
		}
	}

	while (p)
	{
		if (p == q)
		{
			return p;
		}

		p = p->next;
		q = q->next;
	}

	return NULL;
}

2、判断单链表是否有环
解析：单链表根据其特点，一旦有环就不会出环，这里可以运用快慢指针来做，下面画图来说明：


代码：
//判断是否有环并返回交点
static LinkList RingList(LinkList list)
{
	LinkList p = list, q = list;

	while (q != NULL)
	{
		p = p->next;
		q = q->next;
		if (q == NULL)
		{
			return NULL;
		}
		q = q->next;

		if (p == q)
		{
			return p;
		}
	}

	return NULL;
}

LinkList IsRingList(LinkList list)
{
	DeterPointIsNULL(list);

	LinkList pNode = RingList(list);

	LinkList qNode = list;

	while (pNode != qNode)
	{
		pNode = pNode->next;
		qNode = qNode->next;
	}

	return pNode;
}

3、在O(1)下删除一个结点p
解析：由于单链表不能直接得知一个结点的前驱，所以一般采用的方法需要用到O(n)的时间复杂度。要在O(1)下完成，可以另辟新径，把后一个结点的数据值复制到需要删除的结点，然后删除后一个结点，下面画图：


代码：
void DeleteLinkListNode(LinkList list,LinkList p)
{
	if (p == NULL || p->next == NULL)
	{
		return;
	}

	LinkList q = p->next;
	p->data = q->data;
	p->next = q->next;
	free(q);
}

4、在O(1)下添加一个结点在结点p前面
解析：这个的做法与上面类似，主要运用的方法还是向后操作，把新节点添加在后面，通过数据交换来达到向前添加结点的作用，如下图：

代码：
void InsertOfNode(LinkList list, LinkList p, ElemType val)
{
	if (list == NULL || p == NULL || p == list)
	{
		return;
	}

	LinkList s = _ApplyNode(p->data, p->next);

	p->data = val;
	p->next = s;
}

5、逆置单链表
解析：单链表逆置的其实很简单，只需要保证能依次拿到下一个指针并改变顺序即可，下面画图说明：


代码：
void ResverLinkList(LinkList list)
{
	DeterPointIsNULL(list);

	if (list->length < 2)
	{
		return;
	}

	LinkList s = NULL, p = list->next;
	LinkList q = p->next;

	while (p != NULL)
	{
		p->next = s;
		s = p;
		p = q;
		if (q != NULL)
		{
			q = q->next;
		}
	}
}

创建单链表
关于数据结构的入门，就是从顺序表和单链表开始。

我们不讲顺序表，直接从单链表开始我们的数据结构和算法的学习之路。
单链表就是一种特殊的结构体组合而成的数据结构，关于单链表的创建方法有很多种，但都大同小异。

正如这幅图中所表示的那样，单链表就是由可能不连续的数据所组合而成的数据结构。 其中每个数据分为两部分，一部分是数据存储的位置，称为数据域，另外指针所存储的地方，称为指针域。
typedef struct Node {
	int data;                    // 存储链表数据
	struct Node *next;     		//  存储结点的地址
}LNode,*Linklist;

在进入创建链表之前，我们先写好主函数的用来输出的输出函数。
void Illustrate(Linklist head) {
	Linklist tem = head;                 //  将头指针的地址赋给临时的指针
	while (tem->next != NULL) {       //  指向最后一个结点的指针域时会停止
		tem = tem->next;               //  结点不断向后移动
		printf("%d\n", tem->data);
	}
}

int main() {
	Linklist head = NULL;            //  链表的头指针
	head = Creat_list(head);        //  创建链表
	Illustrate(head);               //  输出每个结点的数据域
	system("pause");
	return 0;
}

头插法创建单链表

头插法代码：
Linklist Creat_list(Linklist head) {
	head = (Linklist)malloc(sizeof(Lnode));      //  为头指针开辟内存空间
	Lnode *node = NULL;                    //  定义新结点
	int count = 0;                          //  创建结点的个数
	head->next = NULL;              
	node = head->next;              	//  将最后一个结点的指针域永远保持为NULL
	printf("Input the node number: ");
	scanf("%d", &count);
	for (int i = 0; i < count; i++) {
		node = (Linklist)malloc(sizeof(Lnode));     //  为新结点开辟内存空间
		node->data = i;               //  为新结点的数据域赋值
		node->next = head->next;          //  将头指针所指向的下一个结点的地址，赋给新创建结点的next 
		head->next = node;          //  将新创建的结点的地址赋给头指针的下一个结点
	}
	return head;
}

头插法创建链表的根本在于深刻理解最后两条语句
	node->next = head->next;          //  将头指针所指向的下一个结点的地址，赋给新创建结点的next 
	head->next = node;          //  将新创建的结点的地址赋给头指针的下一个结点

创建第一个结点
执行第一次循环时，第一次从堆中开辟一块内存空间给node，此时需要做的是将第一个结点与 head 连接起来。而我们前面已经说过，单链表的最后一个结点指向的是 NULL。
因此插入第一个结点时，我们需要将头指针指向的 next 赋给新创建的结点的 next ， 这样第一个插入的结点的 next 指向的就是 NULL。 接着，我们将数据域，也就是 node 的地址赋给 head->next， 这时 head->next 指向的就是新创建的 node的地址。而 node 指向的就是 NULL。
接着我们创建第二个结点
因为使用的头插法，因此新开辟的内存空间需要插入 头指针所指向的下一个地址，也就是新开辟的 node 需要插入 上一个 node 和 head  之间。 第一个结点创建之后，head->next 的地址是 第一个 node 的地址。 而我们申请到新的一块存储区域后，需要将 node->next 指向 上一个结点的首地址， 而新node 的地址则赋给 head->next。 因此也就是 node->next = head->next 。

这样便将第一个结点的地址赋给了新创建地址的 next 所指向的地址。后两个结点就连接起来。
接下来再将头结点的 next 所指向的地址赋为 新创建 node 的地址。 head->next = node ，这样就将头结点与新创建的结点连接了起来。  此时最后一个结点，也就是第一次创建的结点的数据域为0，指针域为 NULL。
创建更多的结点也就不难理解。

执行一次：


会发现，头插法创建链表时候，就相当于后来居上。 后面的结点不断往前插，而最后创建的结点在第一个结点处， 第一个创建的结点变成了尾结点。
尾插法创建单链表

尾插法代码：
Linklist Creat_list(Linklist head) {
	head = (Linklist)malloc(sizeof(Lnode));          //  为头指针开辟内存空间
	Linklist node = NULL;           //  定义结点
	Linklist end = NULL;            //  定义尾结点
	head->next = NULL;              //  初始化头结点指向的下一个地址为 NULL
	end = head;                     //  未创建其余结点之前，只有一个头结点
	int count = 0 ;                 //  结点个数
	printf("Input node number: ");
	scanf("%d", &count);
	for (int i = 0; i < count; i++) {
		node = (Linklist)malloc(sizeof(Lnode));          //  为新结点开辟新内存
		node->data = i;                                  //  新结点的数据域赋值
		end->next = node;                      		
		end = node;
	}
	end->next = NULL;
}

尾插法深刻理解：
end->next = node;                      		
end = node;

尾插法创建第一个结点
刚开始为头结点开辟内存空间，因为此时除过头结点没有新的结点的建立，接着将头结点的指针域 head->next  的地址赋为 NULL。因此此时，整个链表只有一个头结点有效，因此 head此时既是头结点，又是尾结点。因此将头结点的地址赋给尾结点 end  因此：end = head。  此时end 就是 head, head 就是 end。 end->next 也自然指向的是 NULL。
尾插法创建第二个结点
创建完第一个结点之后，我们入手创建第二个结点。 第一个结点，end 和 head 共用一块内存空间。现在从堆中心开辟出一块内存给 node，将 node 的数据域赋值后，此时 end 中存储的地址是 head 的地址。此时，end->next  代表的是头结点的指针域，因此 end->next = node 代表的就是将上一个，也就是新开辟的 node 的地址赋给 head 的下一个结点地址。
此时，end->next 的地址是新创建的 node 的地址，而此时 end 的地址还是 head 的地址。 因此 end = node ,这条作用就是将新建的结点 node 的地址赋给尾结点 end。 此时 end 的地址不再是头结点，而是新建的结点 node。
一句话，相当于不断开创新的结点，然后不断将新的结点的地址当做尾结点。尾结点不断后移，而新创的结点时按照创建的先后顺序而连接的。先来新到。
尾插法创建单链表，结点创建完毕
最后，当结点创建完毕，最后不会有新的结点来替换 end ，因此最后需要加上一条 end->next = NULL。将尾指针的指向为 NULL。
创建更多结点也自然容易理解了一些。
执行一次：


总结
由上面的例子以及比较，我们可以看见：

头插法相对简便，但插入的数据与插入的顺序相反；
尾插法操作相对复杂，但插入的数据与插入顺序相同。

两种创建的方法各有千秋，根据实际情况选择不同的方法。
关于链表的相关其他操作，请浏览相关文档。

Java内部也有自己的链表--LinkedList，但是我们今天不是讨论LinkedList，而是自己来实现一个单链表，包括简单的增删查改：

		
单链表的结构
		
单链表的基本操作
		
虚拟头结点的使用
	
整个类的设计如下：
public class Linked <T>{
	
	private class Node{
		private T t;
		private Node next;
		public Node(T t,Node next){
			this.t = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
	}
	private Node head;    		//头结点
	private int size;			//链表元素个数
	//构造函数
	public Linked(){
		this.head = null;
		this.size = 0;
	}
}

单链表的结构

	一种链式存取的数据结构，单链表中的数据是以结点的形式存在，每一个结点是由数据元素和下一个结点的存储的位置组成。单链表与数组相比的最大差别是：单链表的数据元素存放在内存空间的地址是不连续的，而数组的数据元素存放的地址在内存空间中是连续的，这也是为什么根据索引无法像数组那样直接就能查询到数据元素。
[单链表结构图]
链表存储的结点
private class Node{
		private T t;
		private Node next;
		public Node(T t,Node next){
			this.t = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
}

链表的基本操作
包括链表的增删查改，以及判别某结点是否存在链表中
链表结点的增加

进行结点的添加的时候，是根据索引来进行操作的，由于成员变量size记录了当前链表的元素个数，进行某个索引位置的结点插入就会很方便了。先找到该目标索引的前一个结点，记录为pre，把要插入的结点node的下一个结点node.next指向pre的下一个结点pre.next；再把pre.next指向node结点。如果先进行pre.next指向要插入的结点，再进行node.next指向pre.next的话，无疑是要插入的结点自己指向了自己，无法连接上整个链表，在链表的操作中，有时候顺序的执行会带来不一样的结果。
//链表头部添加元素
	public void addFirst(T t){
		Node node = new Node(t);	//节点对象
		node.next = this.head;
		this.head = node;
		//this.head = new Node(e,head);等价上述代码
		this.size++;
	}
	//向链表尾部插入元素
	public void addLast(T t){
		this.add(t, this.size);
	}
	//向链表中间插入元素
	public void add(T t,int index){
		if (index <0 || index >size){
			throw new IllegalArgumentException("index is error");
		}
		if (index == 0){
			this.addFirst(t);
			return;
		}
		Node preNode = this.head;
		//找到要插入节点的前一个节点
		for(int i = 0; i < index-1; i++){
			preNode = preNode.next;
		}
		Node node = new Node(t);
		//要插入的节点的下一个节点指向preNode节点的下一个节点
		node.next = preNode.next;
		//preNode的下一个节点指向要插入节点node
		preNode.next = node;
		this.size++;
	}

链表结点的删除
//删除链表元素
	public void remove(T t){
		if(head == null){
			System.out.println("无元素可删除");
			return;
		}
		//要删除的元素与头结点的元素相同
		while(head != null && head.t.equals(t)){
			head = head.next;
			this.size--;
		}
		/**
		 * 上面已经对头节点判别是否要进行删除
		 * 所以要对头结点的下一个结点进行判别
		 */
		Node cur = this.head;
		while(cur != null && cur.next != null){
			if(cur.next.t.equals(t)){
				this.size--;
				cur.next = cur.next.next;
			}
			else cur = cur.next;
		}
		
	}


在进行链表的结点删除时候，要分情况讨论：
当要删除的结点位于头结点的时候：如下图要删除的元素1的结点位于头结点，先进行while判断头结点是否为null且判断该结点的元素是否为要删除的元素，如果是把head指向head.next即可，直接跳过头结点，直到头结点不是要删除的元素就结束循环。
[要删除的元素1位于头结点]
当要删除的结点不在头结点的时候：如下图删除元素为3的结点，由于上面已经判断了头结点不是要删除的元素，所以我们从头结点的下一个结点开始循环，即cur.next，当cur.next是要被删除的元素时，直接cur.next = curr.next.next就能直接跳过cur.next，断开。

[要删除结点的元素为3的结点]


删除链表的头结点的元素和删除链表的尾结点的元素
//删除链表第一个元素
	public T removeFirst(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		Node delNode = this.head;
		this.head = this.head.next;
		delNode.next =null;
		this.size--;
		return delNode.t;
	}
	//删除链表的最后一个元素
	public T removeLast(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		//只有一个元素
		if(this.getSize() == 1){
			return this.removeFirst();
		}
		Node cur = this.head;	//记录当前结点
		Node pre = this.head;	//记录要删除结点的前一个结点
		while(cur.next != null){
			pre = cur;
			cur = cur.next;
		}
		pre.next = cur.next;
		this.size--;
		return cur.t;
	}

经过上面在进行链表的结点删除的时候，会发现在删除的过程中很麻烦，还得考虑头结点（因为我们在删除结点的时候，都是先找到待删除结点del的前一个结点pre，然后直接进行跳过操作，即pre.next = pre.next.next，但是删除结点头结点的时候就无法操作），给我们添加了麻烦，为此我们可以给链表添加一个虚拟的头结点，说白了就是重新new一个结点对象，该结点对象的下一个结点指向了我们之前的头结点，让我们在删除结点的时候，无须再考虑之前的头结点了！
虚拟头结点删除链表元素的实现
//加入虚拟头结点的链表进行删除
	public void removeElt(T t){
		//构造虚拟头结点，并且下一个结点指向head
		Node dummy = new Node(t,this.head);
		//声明结点指向虚拟头结点
		Node cur = dummy;
		//从虚拟头结点的下一个结点开始遍历
		while(cur.next != null){
			if(cur.next.t.equals(t)){ 
				cur.next = cur.next.next;
				this.size--;
			}
			else cur = cur.next;
		}
		//去除虚拟头结点
		this.head = dummy.next;
	}

使用虚拟头结点进行链表的插入
刚开始那部分的结点添加是基于索引的情况实现，当我们无法知道一个结点的位于链表的哪个位置时候，只知道要插入在某个元素的前面，下面的代码基于上述情况实现。
	/**
	 * 
	 * @param t:插入在t元素的位置
	 * @param des：要插入的元素
	 */
	public void insert(T t,T des){
		//构造虚拟头结点，并且下一个结点指向head
		Node dummy = new Node(null,this.head);
		//构造要插入的结点
		Node dNode = new Node(des);
		//声明变量cur指向虚拟头结点
		Node cur = dummy;
		while(cur.next != null){
			if(cur.next.t.equals(t)){ 
				dNode.next = cur.next;
				cur.next = dNode;
				this.size++;
				break;
			}
			else cur = cur.next;
		}
		this.head = dummy.next;
	}

查找某个元素是否在链表的结点上
//链表中是否包含某个元素
	public boolean contains(T t){
		Node cur = this.head;
		while(cur != null){
			if(cur.t.equals(t)){
				return true;
			}
			else cur = cur.next;
		}
		return false;
	}

完整的代码实现：
package LinkedList;

public class Linked <T>{
	
	private class Node{
		private T t;
		private Node next;
		public Node(T t,Node next){
			this.t = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
	}
	private Node head;    		//头结点
	private int size;			//链表元素个数
	//构造函数
	public Linked(){
		this.head = null;
		this.size = 0;
	}
	
	//获取链表元素的个数
	public int getSize(){
		return this.size;
	}
	//判断链表是否为空
	public boolean isEmpty(){
		return this.size == 0;
	}
	//链表头部添加元素
	public void addFirst(T t){
		Node node = new Node(t);	//节点对象
		node.next = this.head;
		this.head = node;
		// this.head = new Node(e,head);等价上述代码
		this.size++;
	}
	//向链表尾部插入元素
	public void addLast(T t){
		this.add(t, this.size);
	}
	//向链表中间插入元素
	public void add(T t,int index){
		if (index <0 || index >size){
			throw new IllegalArgumentException("index is error");
		}
		if (index == 0){
			this.addFirst(t);
			return;
		}
		Node preNode = this.head;
		//找到要插入节点的前一个节点
		for(int i = 0; i < index-1; i++){
			preNode = preNode.next;
		}
		Node node = new Node(t);
		//要插入的节点的下一个节点指向preNode节点的下一个节点
		node.next = preNode.next;
		//preNode的下一个节点指向要插入节点node
		preNode.next = node;
		this.size++;
	}
	//删除链表元素
	public void remove(T t){
		if(head == null){
			System.out.println("无元素可删除");
			return;
		}
		//要删除的元素与头结点的元素相同
		while(head != null && head.t.equals(t)){
			head = head.next;
			this.size--;
		}
		/**
		 * 上面已经对头节点判别是否要进行删除
		 * 所以要对头结点的下一个结点进行判别
		 */
		Node cur = this.head;
		while(cur != null && cur.next != null){
			if(cur.next.t.equals(t)){
				this.size--;
				cur.next = cur.next.next;
			}
			else cur = cur.next;
		}
		
	}
	//删除链表第一个元素
	public T removeFirst(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		Node delNode = this.head;
		this.head = this.head.next;
		delNode.next =null;
		this.size--;
		return delNode.t;
	}
	//删除链表的最后一个元素
	public T removeLast(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		//只有一个元素
		if(this.getSize() == 1){
			return this.removeFirst();
		}
		Node cur = this.head;	//记录当前结点
		Node pre = this.head;	//记录要删除结点的前一个结点
		while(cur.next != null){
			pre = cur;
			cur = cur.next;
		}
		pre.next = cur.next;
		this.size--;
		return cur.t;
	}
	//链表中是否包含某个元素
	public boolean contains(T t){
		Node cur = this.head;
		while(cur != null){
			if(cur.t.equals(t)){
				return true;
			}
			else cur = cur.next;
		}
		return false;
	}
	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		Node cur = this.head;
		while(cur != null){
			sb.append(cur.t+"->");
			cur = cur.next;
		}
		sb.append("NULL");
		return sb.toString();
	}
	
	public static void main(String[] args) {
		Linked<Integer> linked = new Linked();
		for(int i = 0; i < 10; i++){
			linked.addFirst(i);
			System.out.println(linked);
		}
		linked.addLast(33);
		linked.addFirst(33);
		linked.add(33, 5);
		System.out.println(linked);
		linked.remove(33);
		System.out.println(linked);
		System.out.println("删除第一个元素："+linked.removeFirst());
		System.out.println(linked);
		System.out.println("删除最后一个元素："+linked.removeLast());
		System.out.println(linked);
	}
}


总结：学链表是一种痛苦，但是痛苦并快乐着，希望能够坚持下去，把链表的全家桶都学习了，而不是这么简单的增加和删除。上述如有说的不对的地方欢迎指正！下篇文章将进行用链表实现栈和队列。

无环单链表+有环单链表or有环单链表+无环单链表

判断相交

必定不相交