题目一：两两交换链表中的节点
题目描述：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路分析：使用虚拟头结点，视频指路?
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
// 循环终止条件,注意书写顺序不能改变
while (cur.next != null && cur.next.next != null) {
ListNode temp = cur.next; // 保存节点一
ListNode temp1 = cur.next.next.next; // 保存节点三
cur.next = cur.next.next; // 虚拟头节点指向节点二
cur.next.next = temp; // 节点二指向节点一
temp.next = temp1; // 节点一指向节点三
cur = cur.next.next; // 将cur的位置移动到下个交换节点的前一个位置
}
return dummy.next;
}
}题目二：删除链表的倒数第N个结点
题目描述：给你一个链表，删除链表的倒数第?
n?个结点，并且返回链表的头结点。
思路分析：使用双指针和虚拟头结点，视频指路?
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode();
dummy.next = head; // 不定义虚拟头结点，会造成空指针异常
ListNode fast = dummy;
ListNode slow = dummy;
while (n-- > 0) {
fast = fast.next;
}
fast = fast.next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}?题目三：链表相交
题目描述：给你两个单链表的头节点?
headA?和?headB?，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回?null?。
思路分析：来自力扣某大佬的题解，题解链接
????????求两个链表的相交点，其实可以想到：链表A的长度 + 链表B的长度 = 链表B的长度 + 链表A的长度。如下图所示，相当于两个相同长度的链表A和链表B的拼接。我们同时遍历这两个链表，当节点相同的时候即为相交节点。
具体实现：
设置curA为链表A的头结点
设置curB为链表B的头结点
curA向后移动，遇到空节点将curA指向headB继续向后遍历
curB向后移动，遇到空节点将curB指向headA继续向后遍历
当curA == curB时候则找到相交节点
?
?解法一：神仙代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
while (curA != curB) {
curA = curA != null ? curA.next : headB;
curB = curB != null ? curB.next : headA;
}
return curB;
}
}
// 作为凡人的我只能说一句 “多么优美的代码！”?解法二：双指针（自己对着录友提供的代码实现了一遍，还是没能完全理解）
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0;
int lenB = 0;
// 求链表A的长度
while (curA != null) {
lenA++;
curA = curA.next;
}
// 求链表B的长度
while (curB != null) {
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
int tempLen = lenA;
lenA = lenB;
lenB = tempLen;
ListNode tempNode = curA;
curA = curB;
curB = tempNode;
}
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap-- > 0) {
curA = curA.next;
}
while (curA != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}题目四：环形链表||
题目描述：给定一个链表的头节点 ?head?，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
思路分析：重点在于判断是否有环，并找到环的入口 (这一期carl哥讲的太神了，清晰明了，简单易懂)，视频指路?
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) { // 若有环，则相遇
ListNode index1 = fast;
ListNode index2 = head;
while (index1 != index2) { // 两个指针相等是即为环入口
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}总结：
? ? ? ? 题一是对虚拟头结点的使用，但细节很多，记录了不少注释。
? ? ? ? 题二是虚拟头结点和双指针的运用，要判断好循环条件。
? ? ? ? 题三只能说是膜拜大佬了，我等凡人且避之。
? ? ? ? 题四刷新了解题的认知，当代码与数学解题思路相结合，仿佛了打开了新世界的大门。