// 解法一：双指针拉链法，比较当前指针位所在值的大小，若比较a1和a2时a1>=a2，直接将a2的指针指向a1依次类推
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 定义新链表
ListNode temp=new ListNode(-1);
// 定义头指针
ListNode p=temp;
ListNode p1=list1;// 自己能点出来的，直接赋值就好
ListNode p2=list2;
while(p1!=null && p2!=null){
if(p1.val
2、LeetCode第141题（环形链表【判断是否为环形链表】）【简单】
public class Solution {
public boolean hasCycle(ListNode head) {
// 使用快慢指针，再环形链表中必会相交的特点来判断
// 1.定义快慢指针
ListNode fast=head;
ListNode slow=head;
// 2.(退出循环的条件，一快指针已经null没环；相遇满足成环条件)
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
// 每次走完判断
if(fast==slow){
return true;
}
}
return false;
}
}
3、LeetCode第141题目（判断环形链表交点位置）【中等】
分析：
1、按照套圈问题总结，fast一定是slow的2k倍
2、设slow到相遇点时为k，那么fast为2k
3、设环形起点到相遇点是m=》那么head到环形起点位置为=k-m（slow那一块）
4、那么按照这样计算=》fast的角度出发就是（head到环形起点位置为=2k-k-m）
public class Solution {
public ListNode detectCycle(ListNode head) {
// 交点处，无非就是走完前面一小段到环的位置的地方（如图就是3=》2这段距离）
// 难点解出这段距离的长度
// 使用快慢指针，当相遇时，将任何一个指针返回到头节点，然后再两一个一起走，那么再次相遇的时候，就是目标
// 在代码中指针定义走两倍之差
// 思路如图：假设一个相遇点，想象一下从相遇点截断甩到头头指针位置就是这段目标距离
// 1.定义快慢指针
ListNode fast=head;
ListNode slow=head;
// 2.执行快慢指针的常规操作
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
// 2.1找到相遇点跳出循环
if(slow==fast){
slow=head;
break;
}
}
// 注意判断不成环的情况
if(fast==null||fast.next==null){
return null;
}
// 3.这个时候就一步一步走了,当他们再次相遇时跳出循环
// 3.1记录链表的索引下标位置
int count = 0;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
count ++;
}
System.out.println("index："+count);
return slow;
}
}
4、LeetCode第876题（链表中间节点）【简单】
// 解法一：计算链表的长度后，size/2得中间得位置即可
// 解法二：使用快慢指针的技巧（当速度是两倍的快指针到尾部时，慢指针刚好到中间）
class Solution {
public ListNode middleNode(ListNode head) {
// 使用快慢指针，快指针一次走两步，慢指针一次走一步
// 1、定义快慢指针
ListNode fast=head;
ListNode slow=head;
// 2.遍历
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
}
5、LeetCode第160题（相交链表）【简单】
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
解法分析：
这种解法就是将指针遍历到等长的位置找到对应的交点；
// 解法一：化为等长的链表去找交点
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 概述：找到交点，问题是如何定位
// 难点：两个长度不一样的链表如何将长度变为一样，定位到交点
// 使用双指针，当两个指针到到达末尾时，马上让他们指向另一个链表，当相交时到交点
// 1.定义双指针
ListNode p1=headA;
ListNode p2=headB;
// 2.遍历
while(p1!=p2){
// 2.1判断是后移还是当一个指针到null就指向另一条链表
if(p1==null){
p1=headB;
}else{
p1=p1.next;
}
if(p2==null){
p2=headA;
}else{
p2=p2.next;
}
}
return p1;
}
}
6、LeetCode第19题（删除倒数第n个节点）【中等】
// 法一：遍历找到目标节点，再遍历一边删除
// 难点：1、遍历一次就拿捏它；2、控制虚拟头节点的恰当使用，避免NPE
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 概述：删除倒数第n个节点；就是删除正数第【总长-（n-1）】个节点
// 使用虚假节点和双指针技巧（遍历一次）解决
// 快指针先走n步；然后慢指针再走=》当快指针走到末尾，那么慢指针删除正数第【总长-（n-1）】个节点
// 使用虚假指针避免空指针
ListNode dummy=new ListNode(-1);
dummy.next=head;
// 1.定义快慢指针
ListNode fast=dummy;
ListNode slow=dummy;
// 3.快指针先走n步(这里走n-1步是为了找到目标接节点的前一个节点，便于删除目标节点)
// 可以考虑封装一个方法，去找到对应的节点
for(int i=0;i
7、LeetCode第23题（合并K个升序链表）【困难】==》2022.03.27 23:50 待解决；需要使用更高级的算法和数据结构，学完基础再干 
