资源引用：
leetcode题目：
24.两两交换链表中的节点（24. 两两交换链表中的节点 - 力扣（LeetCode））
19.删除链表的倒数第N个结点（19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode））
面试题02.07.链表相交（面试题 02.07. 链表相交 - 力扣（LeetCode））
142.环形链表Ⅱ（142. 环形链表 II - 力扣（LeetCode））
第一自然周总结：
第一周的训练营告一段落了，数组和链表的内容掌握的都很不错，尤其是链表的内容，今天一天完成，中等题目基本上都能思路非常清晰的解出，有好几道题都是一遍过，当然也遇到了一些出错的时候，能够很及时的用debug解决问题。尽管对边界条件的考虑有所提升，但仍然有提高空间，今天后两题不知道是太晚疲惫了还是什么原因，bug都是出在边界条件的设置上，希望自己能够更加小心谨慎！
回过神来的时候已经错过了S14决赛的第一场，很开心BLG赢了，现在是第二把，很焦灼，虽然来晚了，但我会陪着他们走到最后，加油！
24.两两交换链表中的节点（24. 两两交换链表中的节点 - 力扣（LeetCode））
题目分析：
首先处理边界情况，即链表为空、链表仅有1个节点时直接返回。然后是按照链表长度为偶和为奇进行分类讨论（可能有双指针？）：若为偶，直接从头到尾两两交换；若为奇，末尾指针不变。为便于交换，设计虚拟头节点dumpy。
先设计dumpy节点指向原本的头节点head；
完整思路：
设计前缀节点pre，作为将要交换的node1（pre.next=node1）和node2（node1.next=node2）的前缀，若node1和node2均不为空，则进行交换。先将pre指向node2，然后将node1指向node2.next，最后将node2指向node1则完成交换，将pre置为pre.next.next移动2个结点。
总结：
第一次一遍写对中等题，有点小成就感，临时前缀是个好东西！
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dumpy=new ListNode();
dumpy.next = head;
if(head == null || head.next == null){
return head;
}
ListNode pre = dumpy;
ListNode node1,node2;
while(pre.next !=null && pre.next.next !=null){
node1=pre.next;
node2=pre.next.next;
pre.next=node2;
node1.next=node2.next;
node2.next=node1;
pre=pre.next.next;
}
return dumpy.next;
}
}19.删除链表的倒数第N个结点（19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode））
题目分析：
注意双指针的使用，要删除倒数第N个节点，则需要将指针指向其前缀节点，考虑结合虚拟头结点使用。
左指针从dumpy开始，右指针从dumpy后的第N个结点开始。
注意判断边界条件，如果不合则不删除直接返回。
最终返回dumpy.next
总结：
注意使用dumpy.next进行返回
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dumpy = new ListNode();
if(head == null){
return head;
}
dumpy.next = head;
ListNode left = dumpy;
ListNode right = dumpy;
int index=0;
while(index<n && right.next != null){
right=right.next;
index++;
}
if(right == null){
return head;
}
index=0;
while(right.next != null){
left=left.next;
right=right.next;
}
left.next=left.next.next;
return dumpy.next;
}
}面试题02.07.链表相交（面试题 02.07. 链表相交 - 力扣（LeetCode））：
题目分析：
注意不可通过值相同来判断结点是否相同。
注意处理头结点为空的边界条件。
已知不存在环。
此题使用的是单链表。
仍然考虑使用双指针解决问题，首先通过遍历两个单链表，确定两个链表的长度只差x。
然后将快指针分配给较长的链表，慢指针分配给较短的链表，快指针从第x个结点开始（下标记录从x-1开始），慢指针从头结点开始（下标记录从0开始），循环比较二者是否相同，若相同则退出循环并返回该结点；若不相同，则二者一起向下移动1个结点。
反思：
需要注意，遍历链表必须使用curA和curB指针用于遍历，不能改变头结点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lengthA=0,lengthB=0,x=0;
ListNode curA = headA;
ListNode curB = headB;
if(headA == null || headB == null){
return null;
}
do{
lengthA++;
curA=curA.next;
}while(curA != null);
do{
lengthB++;
curB=curB.next;
}while(curB != null);
curA = headA;
curB = headB;
if(lengthA>lengthB){
x = lengthA - lengthB;
while(x-- > 0){
curA = curA.next;
}
}else{
x = lengthB - lengthA;
while(x-- > 0){
curB = curB.next;
}
}
while(curA != curB && curA.next != null && curB.next != null){
curA = curA.next;
curB = curB.next;
}
if(curA == curB && curA.val != 0 && curB.val != 0){
return curA;
}else{
return null;
}
}
}142.环形链表Ⅱ（142. 环形链表 II - 力扣（LeetCode））
题目分析：
给出头结点，求解入环的第一个结点。环的大小未知，盲目进入可能会陷入死循环，判断是否为入环结点不可用值来判断，双指针能解决这个问题吗？
思路一：快慢指针法
考虑快慢指针，快指针一定会追上慢指针并在某个结点X，并且可以求出环的长度loop。此时从头结点再次出发，算出第一次遇到结点X的长度a。则入环结点i一定满足0≤i<a，且结点i向下走loop次后一定返回自身，从而确定i。
快指针每走2步，慢指针走1步
注意index的边界条件！
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
int speed=0;
ListNode fast = head;
ListNode slow = head;
//边界条件：链表为空直接返回null
if(head == null || head.next == null){
return null;
}
if(head.next == head){
return head;
}
//边界条件：遍历过程中发现无环，退出循环并返回null
while(fast.next != null && slow.next != null){
fast=fast.next;
slow=slow.next;
//使fast指针的速度为slow指针的2倍，迟早会在某个结点X与slow指针相遇
if(speed%2 == 0){
//边界条件：如果遍历过程中发现无环，直接返回null
if(fast.next == null || fast.next == fast){
return fast.next;
}
fast=fast.next;
speed=0;
}
//快慢指针相遇即退出循环
if(fast == slow){
break;
}
speed++;
}
//判断相遇循环是否正常退出，若非正常退出，则直接返回null
if(fast.next == null || slow.next == null){
return null;
}
ListNode X = fast;//保存相遇结点X
ListNode cur = head;//初始化寻址指针cur
int head2X=0;//记录从头结点到结点X的距离
int loop=0;//记录环的长度
//求取从头结点到X的距离
while(cur != X){
cur = cur.next;
head2X++;
}
//从相遇结点出发，求取环的长度
do{
cur = cur.next;
loop++;
}while(cur != X);
int index=0;//寻找入环结点的尝试下标
for(index=0;index<=head2X;index++){
int i = index;
cur = head;//重置cur指针
while(i-- > 0){
cur = cur.next;
}
ListNode indexNode = cur;
i = loop;
while(i-- > 0){
cur = cur.next;
}
if(cur == indexNode){
return indexNode;
}
}
return null;
}
}思路二：优化快慢指针（代码随想录 (programmercarl.com)）
参考代码随想录的思路实现，仔细推理数量关系，能够简化寻找流程，感兴趣的可以阅读原文。