在我数据结构与算法的链表讲解中，我留下了几个链表必须要掌握的操作，掌握看了它们，就基本可以实现 “链表自由” 了。
关于链表的详细讲解，可以跳转到我下面的文章。
【数据结构与算法】-＞数据结构-＞链表-＞LRU缓存淘汰算法的实现
这几个操作分别对应了 LeetCode 上的几道题，我们一起来看看。
这道题的具体描述如下👇
这个题我最开始的想法是用散列表先将这些结点按顺序存储起来，这样可以直接根据键值来找到需要删除的点，并且，也只需要遍历一次，就可以将所有结点存入散列表中，后面直接根据键值来取就好了。
想法是好的，最后时间性能上打败了百分之六十多的人，让我意识到这个程序写得是多么蠢。
这个题其实还可以用一个小技巧来做，就是快慢指针。我们先让一个快指针走 n 次，然后这时候慢指针和快指针一起移动，这样当快指针移动到终点，也就是这条链的尾结点的时候，慢指针刚好到要删除的地方。
为了方便对链表进行操作，我引入了一个哨兵，这样如果要删除的结点是头结点，也不需要做特殊处理。我们直接来看代码。👇
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /* * @lc app=leetcode.cn id=19 lang=java * * [19] 删除链表的倒数第N个节点 */ // @lc code=start /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode pre = new ListNode(0); ListNode fastPoint = pre; ListNode slowPoint = pre; pre.next = head; while (n != 0) { fastPoint = fastPoint.next; n--; } while (fastPoint.next != null) { fastPoint = fastPoint.next; slowPoint = slowPoint.next; } slowPoint.next = slowPoint.next.next; return pre.next; } } // @lc code=end可以看到性能提高了非常多。
我先将这道题的具体描述贴上。
这道题大家很容易想到利用 while 循环，然后对两个有序链表进行逐节点的比较，这个思路比较简单，我一开始也是想不到什么好方法，只能用这种笨蛋解法。我先将我的笨蛋解法贴出来，思路很简单，大家看一下就很容易理解了。
/* * @lc app=leetcode.cn id=21 lang=java * * [21] 合并两个有序链表 */ // @lc code=start /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode(); ListNode tmp = head; ListNode p = l1; ListNode q = l2; while (p != null && q != null) { ListNode cur = new ListNode(); if (p.val < q.val) { cur.val = p.val; p = p.next; } else { cur.val = q.val; q = q.next; } tmp.next = cur; tmp = cur; } while (p != null) { ListNode cur = new ListNode(p.val); tmp.next = cur; tmp = cur; p = p.next; } while (q != null) { ListNode cur = new ListNode(q.val); tmp.next = cur; tmp = cur; q = q.next; } return head.next; } } // @lc code=end思路就是先对两个有序链表进行比较，直到一个链表到尽头了。那么如果还有链表没有被遍历完，因为是顺序的，所以直接将它余下的元素加入到最后的链表中即可。
这个笨蛋解法的耗时是多少呢？
可以看到，时间复杂度和空间复杂度都非常高。
我们这个解法每一次比较之后，都要建立一个新的结点，在 while 循环中不仅浪费了很多时间，也浪费了大量的空间，其实没必要，我们再看看一个更聪明的解法，用递归来解决这个问题。
题目的部分我不再给出，只贴出作答的部分👇
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } }代码比前面的少了非常多，我们再看看性能👇
通过这个递归，最后返回的就是最小的结点，我们也不需要再建立额外的空间，直接将原先的结点连接起来就好。
同样的，我先把题目贴出。
看到这个题我首先想到的就是用一个set集合或者hash table来存储，遍历整个链表，如果有相同的结点存进去，那就说明有环，返回 true，否则返回 false。但是，同样的，我首先可以想到的算法一定不是最好的算法。
我们注意题目里的进阶要求，空间复杂度为 O(1)。那就肯定不可以用 set 集合了，那样复杂度就变成 O(n) 了。
这时候，我们就要用到一个非常巧妙的解决方法，也是我们上面提到过的 快慢指针。那这个快慢指针要怎么用呢？
大家肯定对我们初中学过的追及问题有印象吧？如果你比你追及的对象速度快，那你就一定可以追到它。对应到这道题，我们让快指针每次往前走两格，慢指针每次往前走一格，如果链表中有环的话，快慢指针最后就会进入环中，相当于两个人开始在操场跑圈，那快的人一定会追上慢的人，两个人一定能相见。
放在这个题中，也是同样的思路。我们最后就检测快指针有没有追到慢指针，如果追到了，说明一定有环，如果没有追到，那链表中一定没有环。根据这个思路，我们来写代码。
/* * @lc app=leetcode.cn id=141 lang=java * * [141] 环形链表 */ // @lc code=start /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { if (fast.next == slow) { return true; } fast = fast.next.next; slow = slow.next; } return false; } } // @lc code=end这里我还想直接截个图，因为不仅我的编辑器太漂亮了，这个解法也狠漂亮，非常简洁。
具体题目如下👇
进阶的要求是用迭代或者递归来解决，那我们就不要考虑用一个容器比如 ArrayList 来存放然后反转这种算法了，我们直接来看比较复杂的迭代和递归。
这两个算法在我之前的文章中写过，大家有兴趣可以跳转过去看。
【程序员必修数学课】->基础思想篇->迭代法
【程序员必修数学课】-＞基础思想篇-＞递归（上）-＞泛化数学归纳
【程序员必修数学课】-＞基础思想篇-＞递归（下）-＞分而治之&从归并排序到MapReduce
首先我们先看递归。
/* * @lc app=leetcode.cn id=206 lang=java * * [206] 反转链表 */ // @lc code=start /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode cur = reverseList(head.next); head.next.next = head; head.next = null; return cur; } } // @lc code=end最复杂的地方是下面这句
这其实就是一个反转的过程。
拿上图 4 个这个结点来举例子。
head.next.next 指的就是 4.next.next 也就是 5.next，它等于 head，也就是指向了自己，这个语句就实现了结点 5 指向了 4，然后我们再把 head.next = null，也就是 4 指向 5 给断开，这就实现了反转。
整个递归的过程，返回的 cur 就是 5，也就是最后一个结点，这样所有的反转完成之后，返回的 5 就相当于是这个反转链表的头结点了，也就完成了整个的反转过程。
我们来看看递归的性能👇
时间是很快，但是空间消耗是很大的，因为每一层递归都要消耗系统堆栈空间，所以占用的内存很大。
我们再来看迭代。
public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; ListNode tmp = null; while (cur != null) { tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; }迭代法实现的思想就是每遍历到一个结点，用 cur 标记，然后 pre 是 cur 前面的结点，使得 cur 指向 pre，这样遍历完，到 cur 指向 null 的时候，pre 正好指向尾结点，这样就实现了反转。
迭代法的思路不难理解，大家可以用代码做个参考。
迭代法实现的性能也是很强大，空间消耗比递归法少很多👇
我们先看看这道题的具体描述。
我们要求一个链表的中间结点。经过前面几道题，我们知道了有一个很巧妙的遍历方法，就是快慢指针，这道题简直就是为快慢指针而设的。
要求中间结点，那我们令快指针和慢指针都指向头结点，然后开始遍历。快指针一次走两格，慢指针一次走一格，这样直到快指针遍历到链表末端。如果是奇数个，那快指针刚好指向尾结点，fast.next = null。如果是偶数个，那快指针就指向了尾结点的下一个结点，也就是空，即 fast = null。
所以，我们可以根据这两个边界条件，来判断快指针是否遍历完了整个链表。当快指针遍历完链表之后，由于它每次都比慢指针多走一步，所以慢指针最后指向的就是我们要求的中间结点。
我们直接来看代码👇
/* * @lc app=leetcode.cn id=876 lang=java * * [876] 链表的中间结点 */ // @lc code=start /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode middleNode(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } } // @lc code=end为方便大家看，我再截个图👇
性能测试如下👇
OK，这就是链表的几个重要操作，掌握熟练这些题，我们就在通向链表自由之路上前进了一大截。
