原地逆置单链表：头插法与冒泡法详解

本文档主要讨论了如何在单链表的原地逆置操作中实现两种方法：头插法和冒泡法。这两种技术都是在空间复杂度为O(1)的前提下，对单链表进行逆序处理。 1. **头插法**： - 思路：利用链表头部元素逆序的特点，通过工作指针p和后继指针r进行操作。首先，将头结点从链表中分离出来，然后用p遍历链表，每次迭代都将当前结点N1的后继N2插入到链表的头部，更新指针位置，直到p为空。 - 实现代码： ```c++ void Reverse_L1(Linklist L) { LNode *p, *r; p = L->next; L->next = NULL; // 将头结点与链表分离 while (p != NULL) { r = p->next; // 暂存后继 p->next = L->next; // 将N1的后继插入链表头部 L->next = p; // 更新链表头部 p = r; // 移动p到下一个结点 } } ``` 2. **冒泡法**： - 名称由来：这种方法因其操作流程类似于冒泡排序，但不是直接交换相邻元素，而是逐对结点进行逆序。它涉及到两个工作指针pre和p，以及一个后继指针r，总共有3个指针。 - 思路：每次循环中，将p和pre指向的结点对进行逆置，然后三个指针向前移动。当r为NULL时，表示所有结点都已处理，逆置完成。 - 循环逻辑： - 指针pre、p和r依次指向当前对，执行逆置操作。 - 当r不为空时，继续循环；否则，停止并返回。 在实际操作中，头插法简单明了，只需要一个循环，适用于链表长度大于1的情况。冒泡法虽然涉及更多的指针，但它的操作逻辑清晰，易于理解。两种方法的时间复杂度都是O(n)，n为链表的长度。在实际编程中，选择哪种方法取决于个人偏好和特定场景的需求。