1.24两两交换链表中的节点

参考：代码随想录24两两交换链表中的节点

1.1.题目

1.2.思路

实际上，仔细看上面的图之后还是得到了链表原来那个非常重要的性质：即操作当前节点，一定要通过上一个节点进行访问，因为需要修改上一个节点的next指针新的指向。因此本题虽然是交换相邻的两个节点BC，但是始终会从B的上一个节点A开始操作，即虽然是只交换两个节点，但是操作的时候始终是在操作3个节点，就是因为对链表结构进行修改之后，需要更新其上一个节点的next指针，因此一直需要从A节点开始操作。

比如上面的最后一个图，当交换完1和2之后，cur指向了1的位置，但是实际上下面我们是要交换3和4，此时再次使用原来的套路，1指向4，4指向3，3再指向4后面的那个元素，可见此时仍然是成立的。

1.3.代码实现

1.3.1.对next指针的理解

今天发现在代码编程中对next理解的还是不清晰，有的时候把他认为是当前节点的next指针变量，有的时候又把它理解成当前节点的下一个节点。显然这两种理解都是正确的，但是不同的场景下需要使用切换不同的理解方式，显然很麻烦。比如cur->next = tmp，这个就把next理解成当前节点的指针变量；如果是cur->next->val = 1，这又要把next理解成当前节点的下一个节点。这样切换很难受。

实际上，只需要把next理解成从节点出来的、指向下一个节点的箭头即可。这样理解永远不会出错，而不用区分他到底是指针变量还是指向的下一个节点。所以后面统一记为next箭头。

更新：评论中有人对next指针进行了评价，这促使我对next指针又得到了新的理解。

上面自己说对next指针有两种理解，实际上本质原因就在于next指针是归属于两个节点的，它是链接两个节点的桥梁。对于前一个节点来说，next指针就是它的成员变量，此时它就是一个指针变量，比如cur->next = tmp就是在修改这个变量的值。而对于后一个节点来说，上一个节点的next指向的就是当前这个节点的内存地址，所以如果是cur->next->val = 1，那么此时上一个节点的next就相当于是当前节点，此时next就是指针指向的节点。因此是next指针对前后两个节点的联系，导致了它可以有两种不同的理解。

如果统一把next理解成从当前节点出来的、指向下一个节点的箭头：对于cur->next = tmp，就是修改当前节点的箭头指向的方向，让它指向tmp节点； 对于cur->next->val = 1，就是在访问当前节点的箭头指向的节点的值。

1.3.2.编程中要备份哪些节点的指针？

其实很简单，只要是破坏了链表的索引结构，那么都需要备份节点的指针。什么时候会破坏链表的索引结构呢？其实就是修改next箭头的时候。

因此总结为：修改了某个节点的next箭头，此时该节点的下一个节点索引丢失，因此要备份该节点的下一个节点。

1.3.3.代码实现

class Solution
{
public:struct ListNode{int val;ListNode* next;ListNode(int x): val(x), next(nullptr){}ListNode(int x, ListNode* ptr): val(x), next(ptr){}};ListNode *swapPairs(ListNode *head){ListNode* dummy_node = new ListNode(0);dummy_node->next = head;// 链表举例： [cur, 1, 2, 3, 4]// 索引位置： [cur, 1, 2, 3, 4]ListNode* cur = dummy_node;  // 从虚拟头节点0开始// 要交换的是第1和2个节点，因此他们不能是空while(cur->next != nullptr && cur->next->next != nullptr){// 关于要备份哪些节点，实际上可以先编程后面，发现哪里缺了再在这里备份ListNode* tmp1 = cur->next;ListNode* tmp3 = cur->next->next->next;// 步骤1：cur的箭头指向第2个节点，由于cur的箭头被修改，因此需要备份它原来箭头指向的节点，即tmp1cur->next = cur->next->next;// 步骤2：第2个节点的箭头指向第1个节点，由于第2个节点的箭头被修改，因此要备份它原来箭头指向的节点，即tmp3cur->next->next = tmp1;// 步骤3：第1个节点的箭头指向第3个节点cur->next->next->next = tmp3;cur = cur->next->next;   // 最后，cur跳两个位置，交换下两个节点}return dummy_node->next;  // 返回交换后的链表的头指针}
};

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

参考：代码随想录19删除链表的倒数第N个节点

2.1.题目

2.2.思路

注意这里是求倒数第n个节点，一个比较简单的思路是把原来的链表先遍历一遍，求出来它一共有多少个节点N，然后再把总结点数N减去n，就得到了正向数要删除的是第几个节点N-n。这样再次遍历列表到第N-n个节点，对这个节点进行删除。但是很显然这样两个for循环遍历，复杂度是n^2。

另外一个很好的解法是使用双指针，一个fast和一个slow指针都指向虚拟头节点，然后fast指针先向后移动n，然后fast和slow一起向后移动，直到fast移动到最后一个节点，此时slow也就移动到了要被删除的节点。

class Solution
{
public:struct ListNode{int val;ListNode* next;ListNode(int x): val(x), next(nullptr){}ListNode(int x, ListNode* ptr): val(x), next(ptr){}};ListNode *removeNthFromEnd(ListNode *head, int n){ListNode* dummy_node = new ListNode(0, head);ListNode* fast = dummy_node;ListNode* slow = dummy_node;while(n-- && fast->next != nullptr){fast = fast->next;}// 至此fast->next就是第n个节点while(fast->next != nullptr){fast = fast->next;slow = slow->next;}// 至此fast指向最后一个节点，slow的下一个节点就是倒数第n个节点，就是要被删除的节点ListNode* tmp = slow->next;   // 这里修改了next箭头的指向，因此上面要备份原来的next箭头指向的节点slow->next = slow->next->next;delete tmp;return dummy_node->next;}
};

3.面试题02.07链表相交

参考：代码随想录面试题0207链表相交

3.1.题目

3.2.解答

其实链表相交很简单，一定满足是在后面相交的。所以只需要把两个链表在尾部对齐，然后从短的链表的开头开始遍历，比较两个链表对应节点的指针是否相等， 如果相等就找到了相交点。

class Solution
{
public:struct ListNode{int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}};ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){int len_a = 0;int len_b = 0;ListNode* cur_a = headA;ListNode* cur_b = headB;// 查询AB两个链表的总长度while(cur_a != nullptr){len_a++;cur_a = cur_a->next;}while(cur_b != nullptr){len_b++;cur_b = cur_b->next;}// 把两个指针恢复到头指针cur_a = headA;cur_b = headB;int offset = len_a - len_b;if(offset > 0){while(offset--){cur_a = cur_a->next;}}else{offset = -offset;while(offset--){cur_b = cur_b->next;}}while(cur_a != nullptr){if(cur_a == cur_b){return cur_b;}else{cur_a = cur_a->next;cur_b = cur_b->next;}}return nullptr;}
};

4.142.环形链表II

参考：代码随想录142环形链表II

4.1.题目

4.2.思路

整体思路都是参考代码随想录中的讲解，详细内容去看讲解吧，本题还是比较复杂的，从判断是否有环，到计算环的第一个入口点，都有很多分析。

注意在其中有几个问题：

1. 为什么fast指针走两步，slow指针走一步，如果有环的话他们一定会相遇呢？

其实这个问题根据讲解分为两步：
（1）如果有环，那么一定是fast先进入环。这个很容易理解，因为fast走的快嘛。
（2）当slow指针进入环之后，此时只要fast指针没有立即和slow指针相遇，那么不论fast指针在什么地方，都可以把slow指针认为是在前面运动的指针，然后fast指针就在追slow指针。fast指针每次都比slow指针多走一步，因此fast指针在一步一步的追slow指针，他们之间的距离就是一步一步的在减小，因此他们一定会相遇，最多追赶的次数也就是y+z-1次，其中y+z是环的节点个数。

为什么最多的追赶次数是y+z-1次？因为slow刚进入环的时候，如果fast此时也在环的入口点，此时他们直接就相遇了，不用追赶，追赶次数就是0次。只要fast不在环的入口点，按照上面的理解，此时一律都认为slow指针在前面，fast指针在后面追slow指针。那么追的最大次数也就是fast指针恰好在slow指针的下一个节点上，然后fast指针就要比slow指针多走y+z-1次才能追上slow指针，也就是就差一步就追完一圈，这差的一步就是刚开始的时候fast指针在slow指针的下一个节点导致的。

2. 计算入口节点的时候，为什么slow指针在环内走过的长度只可能是y，而不是n*(y+z) + y呢？即slow指针不可能走完一圈？

其实这个问题在上面的问题中已经得到了解答，就是如果slow在刚进入环的时候如果和fast没有相遇，那么fast就要一步一步的去追slow，而且此时追slow需要的步骤次数最多就是y+z-1次，即不会走完一个环，所以说slow指针被fast指针追上之前，在环内肯定不可能走完一圈，最大的长度也就是走y+z-1步，也就是从环的入口开始，走到环的入口的前一个点，此时恰好被fast追上。实际上，这种情况对应的是在slow刚进入环的时候，fast恰好在环的入口的下一个节点上，然后fast就需要追y+z-1步才能追上slow指针。

3. 最后计算相遇节点的时候，得到的公式是x = (n-1)*(y+z) + z，n=1时x=z，为什么n>1时结果和n=1时结果一样？

其实从分析这个公式就可以知道，即一个指针从起点开始，另一个指针从相遇点开始，每次每人各走一步，最后走完x步以后他们一定会在环的起点相遇。此时如果n>1，就相当于另一个指针在环中等了从head出发的第一个指针很久，在环里绕了很多次了。但是最后的结果他们还是会在环的入口处相遇的。

class Solution
{
public:struct ListNode{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}};ListNode *detectCycle(ListNode *head){ListNode* fast = head;ListNode* slow = head;// 注意这里只判断到fast->next即可，不需要判断到fast->next->nextwhile(fast != nullptr && fast->next != nullptr){// 这里一定要先移动再判断，而不能上来就判断是否相等，因为一开始他俩都是head，肯定是相等的fast = fast->next->next;slow = slow->next;// 找到了环的入口点if(fast == slow){// 让一个新的指针从head出发，然后每次走一步，最终会和slow指针在环的入口点相遇ListNode* new_slow = head;while(new_slow != slow){new_slow = new_slow->next;slow = slow->next;}return new_slow;}}return nullptr;}
};