一、单链表逆置
1、法一
思路：
通过两个辅助指针
p和 q，在遍历链表时逐个反转指针方向。
- p初始化为
第一个有效节点，用于遍历原链表；q初始化为NULL，用于临时保存p的下一个节点。plist->next被置为NULL，表示逆置后的链表初始为空（头节点指向空）。每次迭代中：
q保存p的下一个节点（防止断链）。- 将
p的next指向当前逆置链表的头部（plist->next）。- 更新头节点的
next指向p，使p成为新链表的第一个节点。p移动到q（原链表的下一个节点），继续循环。终止条件
当p为NULL时，说明原链表已全部遍历完毕，逆置完成。关键点说明：
头插法：通过每次将当前节点插入头节点之后，实现链表的逆置。
断链处理：
q临时保存p->next，避免修改p->next后丢失后续节点。时间复杂度：O(n)，仅需一次遍历。
空间复杂度：O(1)，仅使用固定数量的指针变量。
示例流程：
假设原链表为
1 -> 2 -> 3 -> NULL，头节点为H：
- 初始：
H -> 1 -> 2 -> 3，p指向1。- 第一次循环后：
H -> 1 -> NULL，p指向2。- 第二次循环后：
H -> 2 -> 1 -> NULL，p指向3。- 第三次循环后：
H -> 3 -> 2 -> 1 -> NULL，p为NULL，退出循环。
代码实现：
//逆置单链表
void Reverse_list(Node* plist) {
assert(plist != NULL);
assert(plist->next != NULL);
assert(plist->next->next != NULL);
Node* p = plist->next;
Node* q = NULL;
plist->next = NULL;
while (p != NULL) {
q = p->next;
p->next = plist->next;
plist->next = p;
p = q;
}
}
2、法二
思路：
指针初始化
p初始化为第一个有效节点（plist->next），q初始化为第二个节点（p->next）。p->next被置为NULL，表示反转后的新链表的尾节点。迭代反转
r保存q的下一个节点（q->next），防止断链。- 将
q->next指向p，完成局部反转。- 指针
p和q分别向后移动一位，继续处理后续节点。- 循环终止时，
p指向原链表的最后一个节点，即反转后的新链表头。更新头节点
plist->next = p;将头节点的next指向反转后的新链表头。示例流程
假设链表为
头节点 -> 1 -> 2 -> 3 -> NULL：
- 初始状态：
p = 1,q = 2,1->next = NULL。- 第一次循环：
r = 3,2->next = 1,p = 2,q = 3。- 第二次循环：
r = NULL,3->next = 2,p = 3,q = NULL。- 结束循环，
头节点->next = 3，得到头节点 -> 3 -> 2 -> 1 -> NULL。关键点
- 三指针协同：
p、q、r分别用于记录当前节点、下一个节点及临时保存节点，确保反转过程中不断链。- 头节点处理：传入的
plist通常为不存储数据的头节点，反转后仍需保持头节点指向新链表头。- 时间复杂度：O(n)，仅需遍历一次链表；空间复杂度O(1)，仅使用固定数量的指针。
边界情况
若链表为空或仅有一个节点，断言会触发错误。实际应用中需根据需求调整断言条件或添加特殊处理。
代码实现：
void Reverse_list2(Node* plist) {
assert(plist != NULL);
assert(plist->next != NULL);
assert(plist->next->next != NULL);
Node* p = plist->next;
Node* q = p->next;
Node* r = NULL;
p->next = NULL;
while (q != NULL) {
r = q->next;
q->next = p;
p = q;
q = r;
}
plist->next = p;
}二、如何判断两个单链表存在交点
思路：两个链表的指针，分别跑到自身的尾节点，判断是否为同一个尾节点
代码实现：
bool Intersect(Node* plist1, Node* plist2) {
assert(plist1 != NULL);
assert(plist2 != NULL);
Node* p = plist1;
Node* q = plist2;
for (; p->next != NULL; p = p->next);
for (; q->next != NULL; q = q->next);
return p == q;
}三、获取两个单链表的相交点
思路：
该算法的目标是找到两个单链表的相交节点（如果有）。核心思路是通过对齐两个链表的起始位置，然后同步遍历，直到找到相同节点。
步骤分解
检查链表是否相交
调用Intersect(plist1, plist2)函数判断两链表是否相交。若不相交，直接返回NULL。计算链表长度
通过Get_Length函数获取两个链表的长度len1和len2，用于后续对齐操作。对齐起始位置
将较长链表的指针p向后移动|len1 - len2|步，使得剩余未遍历部分与较短链表的长度一致。此时p和q（较短链表的头指针）处于同一起跑线。同步遍历寻找交点
同时移动p和q指针，逐个节点比较。当p == q时，当前节点即为相交节点，返回该节点。关键点
- 时间复杂度：O(m+n)，其中m和n为两链表长度。需遍历两次链表（计算长度+同步查找）。
- 空间复杂度：O(1)，仅使用常数级额外空间。
- 边界条件：处理两链表长度差为0时，直接进入同步遍历阶段。
示例说明
假设链表1为
A->B->C->D，链表2为E->F->C->D（相交于节点C）：
len1=4，len2=4（长度差为0，无需对齐）。- 同步遍历
p（链表1）和q（链表2），第三次移动时p和q均指向C，返回C。
代码实现：
Node* Get_Intersect_Node(Node* plist1, Node* plist2) {
bool tag = Intersect(plist1, plist2);
if (!tag) return NULL;
int len1 = Get_Length(plist1);
int len2 = Get_Length(plist2);
Node* p = len1 >= len2 ? plist1 : plist2;
Node* q = len1 >= len2 ? plist2 : plist1;
//此时p指向较长的单链表的辅助结点，q指向较长的单链表的辅助结点
for (int i = 0; i < abs(len1 - len2); i++) {
p = p->next;
}
//pq同步向后走，直到相遇
while (p != q) {
p = p->next;
q = q->next;
}
return p;
}