24. 两两交换链表中的节点
题目链接：24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
文章讲解/视频讲解：https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
思路
这道题比较绕，需要自己在纸上画一下。
可以采用迭代法来处理，每次迭代以两个节点为单位，这两个节点一前一后分别为pre和curr。另外需要提前获取pre的前一个节点pre_head。在每次迭代过程中，首先存一下curr->next（因为接下来会截断）为tmp，然后将curr指向pre，pre指向tmp，pre_head指向curr。之后进行pre_head、pre、curr的迭代，注意检查节点是否为空。
示意图如下：
C++实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* pre_head = dummyHead, *pre = head, *curr = head->next;
while(curr != nullptr){
ListNode* tmp = curr->next;
curr->next = pre;
pre->next = tmp;
pre_head->next = curr;
pre_head = pre;
pre = tmp;
if(pre == nullptr) break;
curr = pre->next;
}
return dummyHead->next;
}
};
19.删除链表的倒数第N个节点
题目链接：19.删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
文章讲解/视频讲解：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html
思路
最简单直接的想法：遍历获得链表的长度，然后再遍历一遍，找到要删除节点的前一个节点，删除该节点。这样需要两趟。
一趟解决的方法没有想出来，看了卡哥的教程，发现可以用双指针来解决。
指定一个慢指针slow和一个快指针fast，让slow指向正向第一个节点，fast指向正向第n + 1个节点。
当fast遍历到链表最后一个节点时，slow正好指向链表倒数第n + 1个节点，此时删除slow之后的节点即可。
C++实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* slow = dummyHead, *fast = dummyHead;
int i = 1;
while(i < n + 1){
fast = fast->next;
i++;
if(fast == nullptr) return dummyHead->next;
}
while(fast->next != nullptr){
slow = slow->next;
fast = fast->next;
}
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
return dummyHead->next;
}
};
面试题 02.07. 链表相交
题目链接：面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
文章讲解/视频讲解：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html
思路
设置两个指针ptrA、ptrB，分别指向头节点headA和头节点headB。令ptrA、ptrB同时开始迭代，当ptrA指向链表尾部时，掉头指向headB，当ptrB指向链表尾部时，掉头指向headA，ptrA与ptrB相等时，即为两个链表的交点。如果ptrA、ptrB同时等于nullptr，则说明遍历完了两轮，始终没有相等，两个链表没有交点。
C++实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == nullptr || headB == nullptr) return nullptr;
ListNode* ptrA = headA, *ptrB = headB;
while(ptrA != nullptr || ptrB != nullptr){
if(ptrA == nullptr) ptrA = headB;
if(ptrB == nullptr) ptrB = headA;
if(ptrA == ptrB) return ptrA;
ptrA = ptrA->next;
ptrB = ptrB->next;
}
return nullptr;
}
};
142.环形链表II
题目链接：142.环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
文章讲解/视频讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
思路
这道题目首先一个思路是用哈希表。用一个指针来遍历该链表，一边遍历一边把扫过的节点存到哈希表里，如果发现遍历的节点之前在哈希表里存储过，该节点便是链表入环的第一个节点，如果指针最终指向nullptr，则说明无环。
还有一种思路是采用快慢指针，这种思路我之前学习过，再遇到时回想了起来。首先定义一个慢指针slow和快指针fast，慢指针每次+1，快指针每次+2。如果快指针最终指向nullptr，则说明无环，如果快指针追上慢指针，与慢指针相等，则说明有环。这时有一个定量的计算，如下图，设无环的阶段长度为a，有环的阶段中，从入环第一个节点到快慢指针相遇的位置长度为b，环中剩余的长度为c。
快指针走过的长度为慢指针走过长度的二倍，快指针走过的长度为a + b + c + b，慢指针走过的长度为a + b，于是有a + b + c + b = 2 * (a + b)，化简得c = a。这时候就明了了，slow指针如果在环中继续迭代的话，再次迭代到入环节点的距离正好和从头节点到入环节点的距离相等。
只要再设置一个指针tmp指向头节点，让tmp指针和slow指针同时遍历，当tmp指针和slow指针相等时，正好是入环节点处。
C++实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr) return nullptr;
ListNode* slow = head, *fast = head, *tmp = head;
do{
slow = slow->next;
fast = fast->next->next;
}while(fast != nullptr && fast->next != nullptr && slow != fast);
if(fast == nullptr || fast->next == nullptr) return nullptr;
while(tmp != slow){
tmp = tmp->next;
slow = slow->next;
}
return slow;
}
};
