• 欢迎光临~

# 24. 两两交换链表中的节点

#### 视频：https://www.bilibili.com/video/BV1YT411g7br

``````class Solution {
public:
ListNode* temp1;
ListNode* temp2;

while (cur->next != NULL && cur->next->next != NULL)
{
temp1 = cur->next; //记录结点1
temp2 = cur->next->next->next;//记录结点3

cur->next->next = temp1;//2->1
cur->next->next->next = temp2;//1->3

cur = cur->next->next; //cur移至下一组结点的前一位
}
}
};
``````

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

#### 视频：https://www.bilibili.com/video/BV1vW4y1U7Gf

``````class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* temp;

n++; //为了让slow指针停在待删除节点前一位
while (n-- != 0 && fastNode != NULL) {
//快指针 - 慢指针 = n+1
//快指针为NULL时，慢指针在待删除节点前一位
fastNode = fastNode->next;
}

while (fastNode != NULL) {
fastNode = fastNode->next;
slowNode = slowNode->next;
}

temp = slowNode->next;
slowNode->next = slowNode->next->next;
delete temp;

}
};
``````

# 160. 相交链表

#### 文章：代码随想录 (programmercarl.com)

``````ListNode* curA = headA;
int lenA = 0, lenB = 0;
while (curA != NULL) { // 求链表A的长度
lenA++;
curA = curA->next;
}
while (curB != NULL) { // 求链表B的长度
lenB++;
curB = curB->next;
}
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
swap (lenA, lenB);
swap (curA, curB);
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap--) {
curA = curA->next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != NULL) {
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;

``````

# 142. 环形链表 II

#### 视频：https://www.bilibili.com/video/BV1if4y1d7ob

``````class Solution {
public:

while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;

if (fast == slow)
{
ListNode* index1 = fast;
while (index1 != index2)
{
index1 = index1->next;
index2 = index2->next;
}
return index2; //返回环的入口
}
}
return NULL;
}
};
``````
``````//数学推导
slow = x + y; //慢指针每次前进一个单位
fast = x + y + n(y + z); //快指针每次前进一个单位

2(x + y) = x + y + n(y + z);
x + y = n(y + z);
x = (n - 1)(y + z) + z;
``````