链表趣事
一说到链表，就想起上学时候天马行空的思维。记得老师第一次放出链表的数据结构图时，不知怎么的。我就想到了小时候看李连杰主演的少林寺。在戏中李连杰有件兵器，看似是长棍，然后一甩成了三节棍，这个画面一直记忆犹新。所以看到链表的节点通过指针串联起来觉得神似。然后….这节课就没好好学了，哈哈。
链表 VS 数组
提到链表，必然会涉及到一个话题：链表与数组的比较。通过两者的对比记忆，能帮我们快速的了解一些链表的特性。
这里就不得不说下数据的四种存储结构了：
- 顺序存储结构
- 链式存储结构
- 散列存储结构
- 索引存储结构
链表和数组是两种截然不同的内存组织方式，数组作为顺序存储结构，使用的是连续的内存空间，可以利用空间局部性原理，借助 CPU cache进行预读，所以访问效率更高。而链表作为链式存储结构不是连续存储，无法进行缓存，随机访问效率也较低。
但每种数据结构，都有自己的优劣，在这里我们需要分开来考虑。
| 数据结构 | 存储结构 | 优点 | 缺点 |
| 数组 | 顺序存储 | 1. 随机访问性强 2. 查找速度快 |
1. 插入和删除效率低 2. 可能浪费内存 3. 内存空间要求高，必须有足够的连续内存空间 4. 数组大小固定，不能动态拓展 |
| 链表 | 链式存储 | 1. 大小不固定，拓展灵活 2. 内存利用率高 3. 插入删除速度快 |
不能随机查找，必须从第一个开始遍历，查找效率低 |
这里大家看到在链表的第三个优点 插入删除速度快 的地方我打了问号，这是为什么？凡事不能一概而论。举个极端的例子，我们需要分别删除数组和链表的最后一个元素。而数组和链表的数据量巨大。这种情况下，你会认为链表的删除速度比数组快？关于这块的知识网上有很多，就不做copy小能手了，大家有兴趣的可以下来看看。
链表的题目分类
链表题目一般都出在手撕算法的环节，而真正机试时很少考，为什么这么说？
上面我们对比了链表和数组的关系，同样的，链表的解题如果出现在机试中，都是可以转化为列表进行求解后再转回链表，那所谓的删除、逆序、两两交换等在链表中较为繁琐的操作，通过这么转换后还有什么难度呢？
下面来说说链表通常涉及的题目：
- 链表的遍历、插入、删除
- 判断链表是否有环
- 反转链表系列（整体反转、两两反转等）
- 双链表、随机指针链表
总体来说链表的题目趋近于简单，遇到链表题目，初学时最重要的一点就是画图，边画图边理解才是王道。下面让我们来看下这个系列的第一道题目吧。
剑指offerII021.删除链表的倒数第n个结点
https://leetcode-cn.com/problems/SLwz0R/solution/shua-chuan-jian-zhi-offer-day11-lian-bia-tuyw/
难度：中等
题目：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
提示：
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
示例：
示例 1： 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2： 输入：head = [1], n = 1 输出：[] 示例 3： 输入：head = [1,2], n = 1 输出：[1]
分析
遇到这种题多了其实就是公式，数组中有快慢指针，链表同样也可以创建快慢两个指针。
初始右指针先跑N，然后左指针在和右指针开始同步向前。
当右指针到达末尾时：
left.next = left.next.next即可!
这里需要注意，N的取值小于等于链表的长度。
这里就需要排除下当右指针跑了N后，已经超出链表，那么代表链表长度与N相等。
那倒数第N个数就是链表头，此时只需要返回head.next即可。
仔细分析，就是如此简单...
解题：
Python:
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head, n): left = right = head count = 0 while count < n: right = right.next count += 1 if not right: return head.next while right.next: left = left.next right = right.next left.next = left.next.next return head
Java:
/** * 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 removeNthFromEnd(ListNode head, int n) { ListNode left = head; ListNode right = head; int count = 0; for (int i = 0; i < n; i++) { right = right.next; } if (right == null) { return head.next; } while (right.next != null) { left = left.next; right = right.next; } left.next = left.next.next; return head; } }
