数据结构——链表

leetcode链表题库和牛客的题库

数据结构——链表

leetcode题库

题目	描述
2.两数相加（中等）	模拟，一个链表节点存一位数，两个链表相加
19.删除链表的倒数第N个节点（中等）	双指针，l和r指针保持n的距离，r指向链尾时，l就是要删除的前一位 或者用两遍扫描也可以。最好有delete操作
21.合并两个有序列表（简单）	迭代，“哨兵”结点preHead，简化链表的维护（只需要维护一个pre指针）
23.合并k个升序链表（困难）	方案一：顺序执行，不断调用【合并两个有序列表】，时间复杂度O(nm2)，其中n为lists长度，m为每个list的平均长度。顺序执行就是先合并1、2个list然后又成为第1个list，之后又不断合并第1、2个，直到所有合并完毕，访问list元素的次数是一个等差数列 方案二：分治，两两链表合并为一个链表，不断重复这个过程，直到最后只剩一个链表。时间复杂度O(nmlogn)，分治一共logn层，每层都要将所有list的元素访问一次，也就是nm。 方案三：优先队列，利用优先队列自动排序的特点（相当于堆），时间复杂度O(nmlogn)，优先队列每次插入删除的复杂度为O(logn)，一共要插入删除nm次。
24.两两交换链表中的节点（中等）	考验对链表操作的熟悉程度，滑动改变链表的指针指向

牛客网

题单：模板速刷TOP101

题目	描述
BM1 反转链表	反转整个链表，错误教训：当链头变为链尾时，一定要将链头的next指向NULL
BM2 链表内指定区间反转	巧妙利用“前哨”节点，让链头永远不变，避免分情况讨论的麻烦。巧妙利用一个temp指针，在区间内转换指针方向
BM3 链表中的节点每k个一组翻转	BM2的反转方法巧妙高效，但不适用于这题，因为它的使用建立在反转区间在链表长度范围内的条件上。但是这题要求，最后长度不足k的区间，保持原样。所以这就要求需要先遍历链表，获取到长度为k的区间进行反转，长度不足k的区间不做改动。
合并两个排序的链表	“前哨”，递归做法和迭代做法
合并k个已排序的链表	递归分治，优先队列两种做法
BM6 判断链表中是否有环	快慢指针，如果链表有环，那么环一定出现在链尾，也就意味着链表没有NULL，只要设置一快一满两个指针，就一定会相遇（快的每次走两步，满的每次走一步）
BM7 链表中环的入口结点	BM6的进阶，首先判断链表是否有环。如果有环，首先了解一个特点，快指针走的步数是慢指针的两倍。 假设链头到环入口的距离为x，环入口距离相遇点的距离为y，相遇点向后到环入口的距离为z， 且假设快指针在环里转了a圈，慢指针在环里转了b圈。那么就有 x+y+a(y+z) = 2[x+y+b(y+z)]， 整理一下得到：(a-2b)(y+z)=x+y，代表的含义是：从相遇点出发，一个指针在环里转若干圈， 另一个指针从头开始，最终会在原来的相遇点再次相遇；那么在相遇之前，从环入口到相遇点这段路程两个指针是重叠的，由此可以得出两个指针第一个重叠的地方就是环入口。
BM8 链表中倒数最后k个结点	双指针，前后指针，间隔k步
BM9 删除链表的倒数第n个节点	双指针，前后指针，“前哨”结点是处理很多链表问题的很好的技巧
BM10 两个链表的第一个公共结点	双指针，获取链表长度，长的先走，让两条链距离公共点的起点相同
BM11 链表相加(二)	反转链表 + 模拟加法 + 反转链表
BM12 单链表的排序	BM4合并两个有序链表，链表的归并排序，左边界是链表起点，右边界是NULL 递归三要素：终止条件、返回值、本级任务
BM13 判断一个链表是否为回文结构	抓住关键：前序和后序一致即为回文，可以用头插法new一个逆序链表，可以用栈，可以保存到数组中用前后对撞指针
BM14 链表的奇偶重排	一共就两种情况，奇数个节点或者偶数个节点，只要把两种情况的处理方式综合考虑进来，理清逻辑，就很容易解决了。
BM15 删除有序链表中重复的元素-I	前后指针pre和cur
BM16 删除有序链表中重复的元素-II	与BM15相比，难度提升在于，BM15保留了一个重复元素，而这里要把所有都删除，所以需要增加一个指针记录重复元素前一位的元素，用了三个指针pre、cur和nex，函数体里面分为两部分，一个是删除部分，与之对立的是指针前进部分 拓展：如果链表是无序的，则使用哈希表map，统计每个节点值出现的次数

小结

• 链表主要考察点有：一、对链表指针的修改，如反转、删除、合并、分离等等。二、对链表性质的考察，如判断链表是否有环、寻找链表环入口、寻找链表之间的公共节点等等。
• 链表题中常用的技巧有：双指针、前哨节点
• 双指针，又可以分为：快慢指针、前后指针、两条链各一个指针。指针的方向可以是同向间隔k步，同向速度不同、反向
• 前哨节点，涉及到链头可能变动时，增加前哨节点可以减少讨论的情况