链表是线性表的链式存储结构，与数组不同的是，它是用一组任意的存储单元来存储线性表中的数据，存储单元不一定是连续的；链表的长度不是固定的，链表的这个特点使其可以非常的方便地实现节点的插入和删除操作。链表的每个元素称为一个节点，每个节点都可以存储在内存中的不同的位置，为了表示每个元素与后继元素的逻辑关系，以便构成“一个节点链着一个节点”的链式存储结构。

单链表：单链表除了存储元素本身的信息外，还要存储其他的后继信息，因此，每个节点都包含两个部分，第一部分称为链表的数据区域，用于存储元素本身的数据信息，这里用data表示，第二部分是一个结构体指针，称为链表的指针域，用于存储其直接后继的节点信息，这里用next表示。

  class Node<T>{
    T data;//数据域
    Node next;//指针域
  }

单向链表只有指向下一个节点的指针域，所以在访问某个元素的时候，只能顺序遍历；头结点不存储实际的数据元素，用于辅助数据元素的定位，方便插入和删除操作。

一、单链表的添加

如图所示我们要把一个新元素13插入到链表的尾部：

• 第一步找到当前链表的尾部元素；
• 第二步新建一个节点元素14；
• 第三步将第一步找到的元素的 next 指针指向这个新创建的元素；

如图所示我们要把一个新元素1添加到链表的头部：

• 第一步新建一个节点元素1；
• 第二步将这新元素的next 指针指向 head 的 next 指针指向的元素
• 第三步将 head 的 next 指针指向新创建的这个元素

单链表的头部添加法与单链表的插入非常相似，不同的是头部添加法可以直接知道我要插入的位置。

二、单链表的插入

如图所示我们要把一个新元素11插入到10和12之间，需要完成的步骤如下：

• 第一步先找到要插入的位置，即11的前驱元素10；
• 第二步新建一个 Node 节点11；
• 第三步将这个新节点的 next 指针，指向前驱元素10的 next指针指向的元素；
• 第四步将元素10的 next 指针指向这个新元素；

第三、单链表的查找

在单链表中要定位某个元素，我们只能从头结点开始，逐个比对，直到找到一个和他匹配的元素。

四、单链表的常见面试题

1、找出单链表的倒数第K个元素（仅允许遍历一遍链表）

使用指针追赶的方法。定义两个指针fast和slow，fast先走K-1步，然后fast和slow同时继续走。当fast到链表尾部时，slow指向倒数第K个（k大于零同时 K 要小于等于链表的长度）。

如上图链表长度等于五，当 k=3时，倒数第 K 个元素是13，按照上述规则走到第四步的时候，FAST 已经在尾部了，此时LAST 对应元素是13。

2、找出单链表的中间元素（仅允许遍历一遍链表）

使用指针追赶的方法，fast每次走两步，slow每次走一步；当fast到链表尾部时，slow指向链表的中间元素。

3、判断单链表是否有环？

方法一：使用p、q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p == q，则存在环。

方法二、使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样，一样不存在环，不一样就是存在环。

P 指针，指向13这个元素，会有两次，第一次走了两步，这个时候 q 指针如果指向13 也需要两步，这个时候没有任何问题。

P 指针继续走，当从元素15过渡到元素13时，需要走五步，而这个这个时候 q 指针指向13还是需要2步，所以存在环。

4、单链表的逆置

求大佬指点，链表的逆置如何实现