一、单链表逆置

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：

1. 初始：H -> 1 -> 2 -> 3，p 指向 1。
2. 第一次循环后：H -> 1 -> NULL，p 指向 2。
3. 第二次循环后：H -> 2 -> 1 -> NULL，p 指向 3。
4. 第三次循环后：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、法二

思路：

1. 指针初始化
   p初始化为第一个有效节点（plist->next），q初始化为第二个节点（p->next）。p->next被置为NULL，表示反转后的新链表的尾节点。

2. 迭代反转

   • r保存q的下一个节点（q->next），防止断链。
   • 将q->next指向p，完成局部反转。
   • 指针p和q分别向后移动一位，继续处理后续节点。
   • 循环终止时，p指向原链表的最后一个节点，即反转后的新链表头。

3. 更新头节点
   plist->next = p;将头节点的next指向反转后的新链表头。

示例流程

假设链表为 头节点 -> 1 -> 2 -> 3 -> NULL：

1. 初始状态：
   p = 1, q = 2, 1->next = NULL。
2. 第一次循环：
   r = 3, 2->next = 1, p = 2, q = 3。
3. 第二次循环：
   r = NULL, 3->next = 2, p = 3, q = NULL。
4. 结束循环，头节点->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;
}

 三、获取两个单链表的相交点

思路：

该算法的目标是找到两个单链表的相交节点（如果有）。核心思路是通过对齐两个链表的起始位置，然后同步遍历，直到找到相同节点。

步骤分解

1. 检查链表是否相交
   调用Intersect(plist1, plist2)函数判断两链表是否相交。若不相交，直接返回NULL。

2. 计算链表长度
   通过Get_Length函数获取两个链表的长度len1和len2，用于后续对齐操作。

3. 对齐起始位置
   将较长链表的指针p向后移动|len1 - len2|步，使得剩余未遍历部分与较短链表的长度一致。此时p和q（较短链表的头指针）处于同一起跑线。

4. 同步遍历寻找交点
   同时移动p和q指针，逐个节点比较。当p == q时，当前节点即为相交节点，返回该节点。

关键点

• 时间复杂度：O(m+n)，其中m和n为两链表长度。需遍历两次链表（计算长度+同步查找）。
• 空间复杂度：O(1)，仅使用常数级额外空间。
• 边界条件：处理两链表长度差为0时，直接进入同步遍历阶段。

示例说明

假设链表1为A->B->C->D，链表2为E->F->C->D（相交于节点C）：

1. len1=4，len2=4（长度差为0，无需对齐）。
2. 同步遍历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;
}