观察ArrayList 顺序表的源码发现，底层是使用数组实现的。由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
由上图可以看出链表在逻辑上是连续的，但是在逻辑上不一定连续
链表有很多不同的结构：
1.不带头单向非循环
2.不带头单向循环
3.不带头双向非循环
4.不带头双向循环
5.带头单向非循环
6.带头单向循环
7.带头双向非循环
8.带头双向循环
共八种不同的结构
本篇文章主要介绍 不带头单向非循环 的链表结构及其方法的实现。
LinkedList的构造
创建LinkedList的代码示例如下：
LinkedList的常用方法
LinkedList中常用的方法如下：
核心就是遍历链表，所有方法的具体实现如下：
- 删除链表中等于给定值 val 的所有节点
上述方法已经实现，代码示例如下：
- 反转一个单链表。 OJ链接
【解题思路】每个链表中的结点都有自己的地址，假设原链表的指向如下图所示：
实现翻转链表就可以把后一个结点的next域，指向前一个结点，遍历整个链表之后，这样每一个结点的next域就会指向前一个结点，此时head走到了最后一个节点，返回head。实现这些操作后的链表中结点的指向如下图：
- 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。OJ链接
方法一：先求出链表的长度 len，不管长度len 是奇数还是偶数，中间结点就是 head 向前移动 len/2 次后所在的结点。
I. 先求出链表的长度：遍历链表，代码示例如下：
II.求出长度len后，让head结点向前移动 len/2 次，此时head结点指向的就是中间节点，完整代码示例如下：
方法二：使用快慢指针。定义快指针 fast，慢指针 slow ，初始 fast 和 slow 都指向head，fast 一次向前移动两步，slow 一次向前移动一步，当fast走到最后时，此时slow就指向 中间结点。那么fast走到最后的循环终止条件如何设置？ —> 当链表中结点个数为奇数时，fast走完 刚好指向最后一个结点，所以终止条件为 ；当当链表中结点个数为偶数时，fast走完 刚好指向最后一个结点的下一个结点（也就是null），所以终止条件为 。所以只要满足这两个条件中的其中一个就会终止，转换到代码层面为： 因此while()中的条件应该为
【 注意 】这里while() 中的判断条件并不是 ！！！
代码示例如下：
4.输入一个链表，输出该链表中倒数第k个结点
这道题和上一道题一样的思路，也是有两种解决方法。
方法一：求链表长度len ，让head 向后走 len - k 步，此时head 就指向了倒数第K个结点
方法二：还是使用快慢指针，快指针 fast ，慢指针 slow，初始 fast 和 slow 都指向head ，此时需要先让fast 向前走 k-1 步，然后 fast 和 slow 绑着一块向前走，一次走一步，当 fast 走到最后时，slow 就指向了倒数第K个结点.代码示例如下:
- 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ
链接
两个有序链表的合并，一定是要遍历两个链表，最后返回拼接后的链表的头结点，
我们可以定义一个伪结点 newH（用来表示合并后新链表的带头结点），newH.next 中存的是新链表的第一个结点，也是data域最小的结点，所以最终返回的结点为 newH.next 。
定义 tmpH 结点，使 tmpH 指向 newH 所指向的对象，只操作tmpH 的next 域 按照升序来拼接结点，最终返回的是newH.next,此时tmpH已经完成了结点的拼接
遍历两个链表，循环条件为 headA 和 headB 都不为null 。每次比较 headA.val 和 headB.val 的大小，哪个小 就把哪个结点 赋值给 tmpH.next。遍历完成之后，如果其中一个结点不为空，就把 这一个结点 赋给 tmpH.next（原本都是升序链表,连接后 后面也一定是升序）
本人注意：【newH 和 tmpH 的关系理解为 head 和 cur 的关系】
代码示例如下：
- 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
OJ链接
【大体思路】遍历链表head, 将小于 x 的结点放在左边，将大于等于 x 的结点放在右边。最后将左边最后一个结点的 next域 指向 右边第一个结点，完成左右链表的拼接，最终返回 左边第一个结点。
【细节】因为 要返回左边的第一个结点 并 将左边最后一个结点的 next域 指向 右边的第一个结点，因此定义 as 表示左边的第一个结点，定义 ae 表示左边的最后一个结点；定义 bs 表示右边的第一个结点，定义 be 表示右边的最后一个结点。
遍历链表进行判断，如果 cur.val < x ，就将这个节点放在左边位置；否则（cur.val >= x）就将这个节点 放在右边位置。【这里注意】在放入之前要判断此时 左边位置是不是空的，如果是空的就 将 bs 和 be 都指向 cur，此时左边就只有一个结点，这个结点 是头也是尾；如果不是空 ，就尾插。右边位置同样要进行相同判断
遍历完成链表后，还要判断：
此时 bs 是否等于 null ，如果等于 null ，那么就直接返回 as；
再判断 此时 as 是否等于 null ，如果等于 null ，那么就直接返回 bs，不再进行拼接
最终还要判断，ae 的 next域是否为空，不为空要置为空。最最后返回 bs。
代码示例如下：
【思路】
- 找到中间结点
- 反转中间结点之后的结点（尾插）
- 首尾进行比较是否相同
- 输入两个链表，找出它们的第一个公共结点
OJ链接
【思路】分别求出两个链表的长度，求出两个链表的长度差 len，让链表较长的 先走 len 步，这时 两个链表的起始位置相一致，遍历链表判断是否有相同的结点
代码示例如下：
- 给定一个链表，判断链表中是否有环
OJ链接
【思路】一个链表如果有环，那么 fast 走两步，slow 走一步，fast 和 slow 一定会相遇。
以下是 力扣官方题解的详细解释：
本方法需要读者对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。
假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。
我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
作者：力扣官方题解
链接
来源：力扣（LeetCode）
代码示例如下：
到此这篇单向链表排序（单向链表排序算法）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/43163.html