链表趣事
一说到链表，就想起上学时候天马行空的思维。记得老师第一次放出链表的数据结构图时，不知怎么的。我就想到了小时候看李连杰主演的少林寺。在戏中李连杰有件兵器，看似是长棍，然后一甩成了三节棍，这个画面一直记忆犹新。所以看到链表的节点通过指针串联起来觉得神似。然后….这节课就没好好学了，哈哈。
链表 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;
}
}
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
网友评论