- 画图！直观形象，便于理解。
- 引入虚拟“头”结点。
- 不吝啬空间。
- 快慢双指针：
- 判环
- 找链表中环的入口
- 找链表中倒数第n个结点
- 创建一个新结点
- 尾插
- 头插
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
讯享网
示例 2：
讯享网输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
解法(模拟):
算法思路:
两个链表都是逆序存储数字的，即两个链表的个位数、十位数等都已经对应，可以直接相加。在相加过程中，我们要注意是否产生进位，产生进位时需要将进位和链表数字一同相加。如果产生进位的位置在链表尾部，即答案位数比原链表位数长一位，还需要再 new 一个结点储存最高位。
讯享网
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
讯享网输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
解法（模拟）
讯享网
给定一个单链表 的头节点 ，单链表 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
讯享网L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4] 输出：[1,4,2,3]
示例 2：
讯享网输入：head = [1,2,3,4,5] 输出：[1,5,2,4,3]
- 找中间节点;（快慢双指针）
- 中间部分往后的逆序;（双/三指针、头插法）
- 合并两个链表。（双指针）
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
讯享网输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
输入：lists = [] 输出：[]
示例 3：
讯享网输入：lists = [[]] 输出：[]
解法一(利用堆)
算法思路:
合并两个有序链表是比较简单的，就是用双指针依次比较链表 1、链表 2 未排序的最小元素，选择更小的那一个加入有序的答案链表中。
合并 K 个升序链表时，我们依旧可以选择 K 个链表中，头结点值最小的那一个。那么如何快速的得到头结点最小的是哪一个呢？用堆这个数据结构就好，我们可以把所有的头结点放进一个小根堆中，这样就能快速的找到每次 K 个链表中，最小的元素是哪个。
解法二(递归/分治)
算法思路:
逐一比较时，答案链表越来越长，每个跟它合并的小链表的元素都需要比较很多次才可以成功排序。比如，我们有8个链表，每个链表长为 100。逐一合并时，我们合并链表的长度分别为(0,100),(100,100),(200,100),(300,100),(400,100),(500,100),(600,100),(700,100)。所有链表的总长度共计 3600。如果尽可能让长度相同的链表进行两两合并呢?这时合并链表的长度分别是(100,100)x4,(200,200)x2,(400,400)，共计 2400。比上一种的计算量整整少了 1/3。迭代的做法代码细节会稍多一些，这里给出递归的实现，代码相对洁，不易写错。
算法流程:
1.特判，如果题目给出空链表，无需合并，直接返回；
2.返回递归结果。
递归函数设计:
- 递归出口: 如果当前要合并的链表编号范围左右值相等，无需合并，直接返回当前链表;
- 应用二分思想，等额划分左右两段需要合并的链表，使这两段合并后的长度尽可能相等；
- 对左右两段分别递归，合并 [ l , r ] 范围内的链表；
- 再调用 mergeTwoLists 函数进行合并(就是合并两个有序链表)。
讯享网
给你链表的头节点 ，每 个节点一组进行翻转，请你返回修改后的链表。
是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
示例 2：
讯享网输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]
解法(模拟)
算法思路:
本题的目标非常清晰易懂，不涉及复杂的算法，只是实现过程中需要考虑的细节比较多。
我们可以把链表按 K 个为一组进行分组，组内进行反转，并且记录反转后的头尾结点，使其可以和前、后连接起来。思路比较简单，但是实现起来是比较复杂的。
我们可以先求出一共需要逆序多少组(假设逆序 n 组)，然后重复 n 次长度为 k 的链表的逆序即可。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/186009.html