22. 两两交换链表中的节点

leetcode链接：两两交换链表中的节点

文档讲解：两两交换链表中的节点

视频链接：代码随想录-两两交换链表中的节点

状态：先看的讲解视频，理解后就写出来了，估计不先看讲解很难写出来；

思路：

1、首先，两两交换相邻的两个节点，我们需要先创建一个虚拟头节点来进行操作（为了让操作更统一，如果不借助此，交换的情况还需要区分交换的节点是否包含头节点，代码会显的乱）；需要借助一个curNode指针来帮我们完成整个遍历操作，他需要指向两个交换节点的前一个节点；另外我们还会借助两个指针temp和temp1（如下图）来帮助我们完成两两交换；

2、交换的思路我们分成三步：a. 首先将curNode.next指向curNode.next.next，但是我们做这一步前，需要先借助temp指针来保存节点1，因为如果我们不保存，当我们做完curNode.next指向curNode.next.next之后，无法对节点1进行操作；b.然后将curNode.next.next = temp,如下图中的步骤2，这时候temp就起到了作用，但是这时候又有新的问题，当我们调整了原节点2的next后，又无法操作节点3了，所以这就是我们事先用temp1保存对节点3的操作；c.最后一步就是将temp.next指向temp1；经过以上三步就实现了节点1和节点2的交换，当处理完节点1和节点2之后，curNode应该调整为curNode.next.next，即指向如下图的节点3的位置上；

3、最后还得考虑什么时候遍历结束的问题，当链表的长度是偶数的时候，curNode.nextnull时遍历就结束了，如果长度是奇数，那么当curNode.next.nextnull的时候遍历结束；所以我们的遍历条件应该为while(curNode.next!=null&&curNode.next.next!=null)。

代码：

class Solution {public ListNode swapPairs(ListNode head) {//创建一个虚拟头节点ListNode dummyHead = new ListNode();dummyHead.next = head;//创建一个指针，该指针指向需要交换的两个元素的前一个元素；ListNode curNode = dummyHead;//链表遍历结束表达式,如果链表长度是偶数，两两进行交换，那么当curNode.next = null时循环结束//如果链表长度是奇数，那么当curNode.next.next=null时循环结束while (curNode.next != null && curNode.next.next != null) {ListNode temp = curNode.next; //用于临时存储需要交换的第一个元素ListNode temp1 = curNode.next.next.next; //用于临时存储交换元素的第二个元素的next；防止调整第二个交换元素next后，找不到原next；//交换操作,最好画图帮助理解；curNode.next = curNode.next.next;curNode.next.next = temp;temp.next = temp1;curNode = curNode.next.next;}return dummyHead.next;}
}

19. 删除链表的倒数第N个节点

leetcode链接：删除链表的倒数第N个节点

文档讲解： 删除链表的倒数第N个节点

视频链接：代码随想录-删除链表的倒数第N个节点

状态：自己写出来了，明天看看视频讲解，看看和视频里的思路是不是一样的；

size-n方式删除

思路：

1、这种方式其实是我第一时间想到的，思路也很简单，先获取到链表的长度，然后找到要删除节点的前一个节点实现删除；

代码：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//先找到链表的长度int size = 0;ListNode curNode = head;while (curNode != null) {size++;curNode = curNode.next;}if (size == 0) {return head;}//删除单链表的节点需要找到要删除节点的前一个节点,但是如果要删除的是头节点，则不会有前一个节点，为了保证规则统一，创建一个虚拟头结点；int preNodeIndex = size - n;if (preNodeIndex < 0) {return head;}ListNode dummyHead = new ListNode();dummyHead.next = head;curNode = dummyHead;for (int i = 0; i < preNodeIndex; i++) {curNode = curNode.next;}curNode.next = curNode.next.next;return dummyHead.next;}
}

双指针方式（推荐）

思路：

1、看了视频讲解之后，觉得此方法很妙，其实按照视频里的方法逆向思考了下，要删除倒数第N个节点，说明要删除节点和最后一个节点的距离是N-1，那么最后一个节点离要删除节点的前一个节点的距离就是N；

2、那么此时，我们想象有个长度N的窗口，窗口从最左边往最右边移动，当窗口的最右边指向链表的最后一个元素的时候，窗口的左边就只想要删除的节点的前一个节点；

代码：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if (head==null) {return head;}ListNode dummyHead = new ListNode();dummyHead.next = head;//定义快慢节点ListNode fastNode = dummyHead;ListNode slowNode = dummyHead;//从dummyHead开始出发，让快节点先移动n步；while (n>0&&fastNode.next!=null) {fastNode = fastNode.next;n--;}//快指针移动n步之后，快慢指针此时同时移动while (fastNode.next!=null) {fastNode = fastNode.next;slowNode = slowNode.next;}slowNode.next = slowNode.next.next;return dummyHead.next;}
}

面试题 02.07. 链表相交

leetcode链接：链表相交

文档讲解：链表相交

视频链接：无

状态：看了文档讲解后写出来了，一开始老去考虑比较值去了，应该站在两个链表相交的角度来看待的，这个题还挺有意思的；明天对比一下写的代码和文档讲解的代码是否相似；

思路：

1、这一题的思路看了解析之后挺简单的，先获取到两个链表的长度；然后分别定义两个指针tempA和tempB指向链表的头节点；将两个指针按照长度对齐；对齐之后，两个指针同时移动，判断tempA==tempB,如果两个指针指向的是同一个节点，则说明有相交节点，直接返回，如果没有找到，则返回null；

代码：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//此题的关键在于，要想清楚，相交节点的判断是要比较两个节点的地址是否相同，而不是值int aListSize = 0;int bListSize = 0;//先找到链表的长度ListNode curNode = headA;while (curNode!= null) {aListSize++;curNode=curNode.next;}curNode = headB;while (curNode!= null) {bListSize++;curNode=curNode.next;}//定义两个指针对齐向后查找ListNode tempB = headB;ListNode tempA = headA;//指针对齐操作，如果a链表比b链表长if (aListSize > bListSize) {int sub = aListSize - bListSize;//因为链表a比b长，所以tempA需要先对齐；for (int i = 0; i < sub; i++) {tempA = tempA.next;}} else {int sub = bListSize - aListSize;//因为链表b比a长，所以tempB需要先对齐；for (int i = 0; i < sub; i++) {tempB = tempB.next;}}//开始查找；while (tempA != null && tempB != null) {//判断tempA和tempB是否相同；if (tempA == tempB) {return tempA;}tempA = tempA.next;tempB = tempB.next;}//没找到返回nullreturn null;}
}

142. 环形链表II

leetcode链接：环形链表II

文档讲解：环形链表II

视频链接：代码随想录-环形链表

状态：自己暴力解法写出来了，强烈推荐看视频解析，这道题好有意思；

暴力解法

思路：

1、自己一刷的时候想出来的，思路很简单，如果链表中存在环形链表，那么我借助一个Set集合（无序，不可重复）和一个遍历指针，每遍历一个节点就放入set集合中，如果有一个节点放入时发现已经存在了，说明有一个节点重复了，这个节点就是环链的入口；属于瞎猫碰到死耗子做出来了；

代码：

public class Solution {public ListNode detectCycle(ListNode head) {if (head == null || head.next == null) {return null;}Set<ListNode> nodeSet = new HashSet<ListNode>();ListNode curNode = head;while (curNode!=null) {if (nodeSet.contains(curNode)) {return curNode;} else {nodeSet.add(curNode);curNode = curNode.next;}}return null;}
}

快慢指针（推荐）

思路：

1、我们定义分别定义好快慢指针fast，slow，同时他们分别按照每次移动两位和移动一位的方式向前遍历；如果链表存在环链，那么fast和slow肯定会在环链的某个节点相遇，那么如果把head到环链入口的距离设置为x，环链入口到相遇点的距离设置为y，相遇点到环链入口的距离设置为z；此时需要印证出两个推论，如果有环链，那么slow肯定在没走完一圈的情况下会被fast追上（至于为什么，有数学论证，可以看视频或者自己实验）；

那么相遇时我们可以得到：slow(走过的距离) = x+y； fast(走过的距离) = x+y+n(圈数)*(z+y);

因为相遇两个指针时间是一样的，fast的速度是slow速度的两倍，那么可以得到：

2(x+y) = x+y+n(z+y) => x+y = n*(z+y) => x = n*(z+y) - y => x = (n-1)(z+y) + z => x=z**

（此处可以想象把整个距离铺开，仔细体会为什么x=z)；

2、经过1的分析，我们代码的思路就是，先定义快慢指针，然后找到相遇点，找到相遇点temp1之后，再定义一个指针temp2=head，让temp1和相遇点2同时遍历，直到temp1==temp2时返回；

代码：

public class Solution {public ListNode detectCycle(ListNode head) {if (head == null) {return head;}ListNode fast = head;ListNode slow = head;while (fast.next!=null && fast.next.next!=null) {fast = fast.next.next; //速度2slow = slow.next; //速度1if (fast == slow) { //说明存在环形链表,此时fast和slow都指向相遇点ListNode temp1 = head;ListNode temp2 = fast;while (temp1 != temp2) {temp1 = temp1.next;temp2 = temp2.next;}return temp1;}}return null;}
}