单链表反转解析：三种方法详解

"这篇资源主要讨论了四种不同的方法来反转单链表，包括将链表转化为数组再逆序、使用三个指针、递归以及一个更直观的双指针法。其中，数组方法浪费空间，而其他方法在时间和空间效率上更优。特别是递归方法，利用了链表的自相似性，可以有效地解决链表反转问题。提供的代码示例展示了如何用双指针法实现链表反转。" 单链表是一种基础的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的引用（或称为指针）。反转单链表意味着将原链表中的前后顺序颠倒，例如原链表1->2->3->4反转后变为4->3->2->1。 **方法1：数组反转** 首先，将链表的所有元素存入数组，然后反向遍历数组，重新建立链表。这种方法简单易懂，但缺点是需要额外的空间存储数组，不适用于大规模数据。 **方法2：三指针法** 这种方法使用三个指针p、q和r。初始时，p指向头节点，q指向下一个节点，head的next指针设为NULL。然后在循环中，每次迭代都将q指向的节点指向前一个节点p，p移动到q的位置，q移动到r的位置，r更新为q的下一个节点。当q为空时，p成为新的头节点。这种方法不需额外空间，但逻辑相对复杂。 ```cpp ActList* ReverseList2(ActList* head) { if (NULL == head || NULL == head->next) return head; // 少于两个节点无需反转 ActList* p; ActList* q; ActList* r; p = head; q = head->next; head->next = NULL; while (q) { r = q->next; q->next = p; p = q; q = r; } head = p; // 返回p作为新的头指针 return head; } ``` **方法3：两指针法（迭代）** 这种方法与三指针法类似，但使用两个指针p和q。p始终指向当前节点，q始终指向p的下一个节点。每次迭代时，p的next指针指向q的下一个节点，然后p和q都向前移动一位，直到q到达链表末尾。这种方法同样不使用额外空间，且逻辑稍显简洁。 **方法4：递归** 利用链表的递归性质，可以将链表反转视为将头节点后面的子链表反转，然后连接到头节点的前面。递归的基本步骤是：反转子链表，然后将头节点插入到子链表的前面。递归终止条件是链表为空或只有一个节点。 ```cpp ListNode* reverseList(ListNode* head) { if (head == NULL || head->next == NULL) return head; ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = NULL; return newHead; } ``` 递归方法简洁，但需要注意递归深度可能导致栈溢出的问题。 反转单链表是一个经典的算法问题，可以锻炼对链表操作的理解。在实际应用中，通常会根据空间和时间复杂度的要求选择合适的方法。递归方法虽然优雅，但需要考虑到递归深度的影响；而迭代方法虽然代码稍多，但在大多数情况下是更优的选择。