链表 算法
# 链表
1: C++ 使用的链表的数据结构
ListNode* head
head->val : 值域
head->next: 指针域
2: 链表创建哑节点
ListNode* dummy = new ListNode(-1);
3: 链表中创建一个游标去遍历链表元素
ListNode* cur = head; // 先指向当前链表的头节点
cur = cur->next; // 游标移动
遍历结束条件是非空： while(cur) {}
4: 删除链表操作 node->val = 0; node->next = nullptr; free(node);
5: 打印链表元素
从头到尾打印链表元素： 遍历链表每个节点，找个数组存放每个节点数据。之后打印数组元素。
从尾到头打印链表元素： 从尾到头，栈先进后出。 遍历链表，找个栈存放节点数据，之后打印栈元素。
6: 环
约瑟夫环： cur指向头节点，找到目标节点后，删除节点。更新新的头节点head，cur重新指向新的头节点。
链表是否带环
（1） 使用快慢指针，当快慢指针相遇时候就说明有
链表环的入口
（1） 使用快慢指针，当两者相遇。 一个重新开始一步步走，一个从相遇点开始走，当再次相遇就为环的入口。
7: 链表反转问题 （需要一个pre 前驱节点）
模版
ListNode* reverse_listnode(ListNode* pre, ListNode* tail)
{
// 注意这种方法 要求pre 不能为空 pre = dummy
// 参数为前驱 和 后继
// pre不动
ListNode* cur_pre = pre; // cur_pre为移动的pre
ListNode* cur = cur_pre->next; // cur 指向当前等待翻转的第一个元素
// 翻转
ListNode* tmp = nullptr;
while (cur != tail) {
tmp = cur->next; // 存放下个节点
cur->next = cur_pre; // 修改指向
cur_pre = cur; // 当前前驱
cur = tmp; // 移动到下个待翻转的节点
}
// 翻转后的结果
ListNode* new_tail = pre->next; // 新的尾
new_tail->next = tail; // 新的尾指向当前cur (或者写为 pre->next->next = tail) 当前cur 指向了当前后驱tail
ListNode* new_head = cur_pre; // 新的头
pre->next = new_head; // 前驱指向新的头
return new_tail; // 返回新的尾部
// return new_head; // 返回新的头部
}
8: 链表双指针问题（快慢指针问题： （1）求是否为环， （2）求环的起点， （3）求倒数第k个节点） （4）链表的中间节点
模版
case 1/2:
// 快慢指针从相同的起点开始，每次快都是慢的2倍。（每次多走一步）
// 结束遍历条件是快指针结束, 指向nullptr.
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr) { // 快指针还没有结束
slow = slow->next;
fast = fast->next;
if (fast->next != nullptr) {
fast = fast->next; // 快指针多走一步
} else {
// (1) return false; // 不是环
// (2) return nullptr; // 不是环 找不到环的起点
}
// 快慢指针两者相遇
if （fast == slow）{
// （1）return true; // 是环
// （2）求环的起点
while (cur != slow) {
slow = slow->next;
cur = cur->next;
}
return slow; // 返回环的起点
}
}
case 3
// 快指针先领先慢指针k步。之后两者一起移动。
// 遍历结束条件是快指针结束，指向nullptr
ListNode* slow = head;
ListNode* fast = head;
int i = 0;
while (i < k) {
fast = fast->next
i++;
if (i != k && fast == nullptr) {
return slow; // 没有移动完 就遍历结束 所以不存在倒数第个节点
} else if (i == k && fast == nullptr) {
return slow->next; // 头节点就是倒数第k个节点 之后返回头节点的下一个节点，实现删除目标节点
}
// 继续
}
ListNode* pre = nullptr;
while(fast) { //fast
pre = slow;
slow = slow->next;
fast = fast->next;
}
pre->next = slow->next; //实现删除slow
case 4 (当都指向head 那么就是偶数中心的后者)（都指向pre 就是指向中心的前者）
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow; // 返回中间节点
链表leetcode:
(1) 反转链表
https://leetcode.cn/problems/reverse-linked-list/
(2) 反转链表
https://leetcode.cn/problems/reverse-linked-list-ii/
(3) 两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/
(4) k个一组交换链表节点
https://leetcode.cn/problems/reverse-nodes-in-k-group/
(5) 回文链表
https://leetcode.cn/problems/palindrome-linked-list/