单链表查找原理,有序单链表查找方法

单链表的头部添加法

如图所示我们要把一个新元素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个元素

如上图链表长度等于五，当 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一样，一样不存在环，不一样就是存在环。