转载自https://leetcode-cn.com/circle/article/YGr54o/
（一）双指针思路：
19. 删除链表的倒数第N个节点：
快慢指针法：设置虚拟节点 dummy指向 head，设定双指针 fast 和 slow，初始都指向虚拟节点 dummy。移动 fast，直到 slow 与 fast 之间相隔的元素个数为 n ，再同时移动 slow 与 fast，直到 fast 指向的为 NULL，将 slow 的下一个节点指向下下个节点即可。
86. 分隔链表
双指针法，before_head 链表存放比 x 小的节点，after_head 链表存放比 x 大于或等于的节点，我们分别用 before 和 after 来前面两个链表添加节点，用 head 来遍历原始链表。当原始链表遍历完成时，我们需要将 before_head 链表连接上 after_head 链表，即 before->next=after_head->next;after->next=nullptr;
92. 反转链表 II※※
双指针法，第一步：找到待反转节点的前一个节点。
第二步：反转m到n这部分。
第三步：将反转的起点的next指向反转的后面一部分。
第四步：将第一步找到的节点指向反转以后的头节点。
：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/ji-bai-liao-100de-javayong-hu-by-reedfan-6/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode node = dummy;
//找到需要反转的那一段的上一个节点。
for (int i = 1; i < m; i++) {
node = node.next;
}
//node.next就是需要反转的这段的起点。
ListNode nextHead = node.next;
ListNode next = null;
ListNode pre = null;
//反转m到n这一段
for (int i = m; i <= n; i++) {
next = nextHead.next;
nextHead.next = pre;
pre = nextHead;
nextHead = next;
}
//将反转的起点的next指向反转的后一部分
node.next.next = next;
//需要反转的那一段的上一个节点的next节点指向反转后链表的头结点
node.next = pre;
return dummy.next;
}
}
109. 有序链表转换二叉搜索树
快慢指针法：问题的关键是找到链表的中间元素，使用两个指针，慢指针每次向后移动一个节点，快指针每次移动两个节点。当快指针到链表的末尾时，慢指针正好访问到链表的中间元素。这时候把中间位置的节点的值作为二叉搜索树根节点的值。（因为二叉搜索树对应的就是一个有序数组，根节点对应的元素值为为有序数组最中间的位置。），然后将链表从中间元素的左侧断开，递归调用即可。
141. 环形链表
快慢指针法：定义两个指针，一快一慢，快指针每次走两步，慢指针每次走一步。如果链表中不存在环，最终快指针将会最先到达尾部，此时返回 false。如果链表中存在环，那么快指针最终一定会追上慢指针。
142. 环形链表 II
快慢指针法：定义两个指针，一快一慢，快指针每次走两步，慢指针每次走一步。如果链表中不存在环，最终快指针将会最先到达尾部，此时返回 false。如果链表中存在环，那么快指针最终一定会追上慢指针。然后相遇之后将 fast 指针指向头节点，slow 指针指向相遇点，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。
143. 重排链表
双指针法：首先重新排列后，链表的中心节点会变为最后一个节点，所以需要使用快慢指针法找到链表中间节点，分割成左右两个链表，反转右半部分链表，依次连接两个链表节点即可。
160. 相交链表
双指针法：指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时，长度差就消除了。
通俗来讲的意思是：我先走我的路，再走你的路，你先走你的路，再走我的路，这样咱俩走的路程就一样了，速度一样，那么肯定在咱俩两条路的交叉口相遇，并一起走向终点。
206. 反转链表
双指针法：指针 pre 用来表示前驱节点，指针 cur 用来遍历链表，每次循环改变将 pre->cur 的方向改变为 pre<-cur，直到遍历结束。
234. 回文链表
快慢指针法：使用快慢指针找到链表中点，反转链表后半部分，比较两个半长链表
是否相同。
876. 链表的中间结点
快慢指针法：使用快慢指针找到链表中点。while(fast != null && fast.next != null)
（二）链表经典题目
2. 两数相加
模拟题，由于链表是逆序存放数字的，所以链表数字从左至右低位对低位，高位对高位，因此我们从左至右遍历两个链表模拟加法运算即可，注意向高位进位。
21. 合并两个有序链表
模拟题，每次循环比较 l1->val和l2->val，若 l1->val<l2->val，则在 cur 后面添加 l1；否则在 cur 后面添加 l2。
23. 合并K个排序链表困难(没做过)
方法1：分治法，将 k 个链表利用二分分为 k 个独立子链表，然后两两进行合并，最后形成一个排序链表。方法2：优雅的暴力法，利用队列 queue 来实现两两链表的组合，首先将队列前两个链表合并成一个，然后添加到队列的尾部，直到队列中只有一个链表时，表示 k 个链表已经合成了。
24. 两两交换链表中的节点中等
简单递归，每次递归交换 head 与 next 即可，也就是完成了两两交换链表中的节点。
25. K 个一组翻转链表困难(没做过)
分治法，将链表按长度 k 进行分组，然后每次翻转长度 k 的链表，注意翻转了长度 k 的链表后新链表的尾部还要连接未翻转部分。
61. 旋转链表中等
模拟题，先求出链表长度 size，若 k 取余 size 为空，那么不用旋转了，直接返回 head；否则先让快指针走 k 个位置，然后两个指针一起走完整个链表。这时，两个指针之间的区域就是我们要移动的区域，只要更改指针指向，就完事了。
即，first->next 指向 head，完成旋转（当然还没完事）；
head 指向 second->next，头结点指向确认；
second->next 指向空节点，尾结点指向确认；
打完收工。
链接：https://leetcode-cn.com/problems/rotate-list/solution/shou-hui-man-hua-tu-jie-leetcodezhi-xuan-zhuan-lia/
82. 删除排序链表中的重复元素 II
模拟题，遍历链表，若 head 的节点值与 head 的 next 节点值不相等，则 pre 指向 head，也就是不重复节点；若相等，我们需要找到重复值子链表的最后一个节点，然后令 pre 指向 head->next，同时 head 移动到下一个节点。
83. 删除排序链表中的重复元素简单
模拟题，直接遍历链表，遇到重复值的节点删除即可。
138. 复制带随机指针的链表
模拟题，分三步，第一步在原链表的每个节点后面拷贝出一个新的节点，第二步拷贝 random，第三步断开链表。
203. 移除链表元素简单
模拟题，直接遍历链表确定是否删除节点即可。
445. 两数相加 II
逆序处理所有数位，使用两个栈法，将两个链表节点值全部压入栈中，然后每次去栈顶元素进行相加，因为这样保证了低位和低位相加，不会出现错位现象。最后直到两个栈为空且进位为 0 为止，就表示相加完成了。
725. 分隔链表(没做出来)
模拟题，首先求出链表的长度，然后根据k来求得每段链表的平均长度，顺便求出余数。由于题目要求每部分长度相差不能超过 1，而且排在前面的部分长度要大于后面部分的长度，所以我们根据余数的个数，给排在前面的部分长度 +1。
430. 扁平化多级双向链表(没做出来)
模拟题，迭代法，遍历链表，若发现该链表存在 child 节点那么就将 [child,tail]` 这段子链表插入到当前节点的后面去，然后继续遍历链表。
817. 链表组件(没有做)
模拟题，如果当前的节点在列表 G 中，并且下一个节点不在列表 G 中，我们就找到了一个组件的尾节点，将 res 加 1。
1171. 从链表中删去总和值为零的连续节点
模拟题，直接遍历链表进行删除和为 0 的连续子链表。
网友评论