单向链表高效逆序输出实现

"这篇文档主要讨论了如何高效地实现单向链表的逆序输出，提供了两种不同的实现方法，一种是迭代方式，另一种是使用栈的递归方法。" 在计算机科学中，链表是一种常用的数据结构，尤其在处理动态数据集合时。单向链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。逆序输出单向链表意味着将链表中的元素顺序反转，原本头部的元素变为尾部，原本尾部的元素变为头部。 首先，我们来看迭代方式的实现。这种方法的核心思想是通过三个指针`pleft`、`pcurrent`和`pright`来辅助操作。初始时，`pleft`为空，`pcurrent`指向头节点，`pright`指向头节点的下一个节点。在循环中，每次将`pcurrent`节点的`next`指针指向前一个节点`pleft`，然后更新这三个指针，直到`pright`为空。最后，遍历调整后的链表并输出。 ```cpp typedef struct node { int data; struct node* next; node(int d): data(d), next(NULL) {} } node; void reverse(node* head) { if (head == NULL) { return; } node* pleft = NULL; node* pcurrent = head; node* pright = head->next; while (pright) { pcurrent->next = pleft; node* ptemp = pright->next; pright->next = pcurrent; pleft = pcurrent; pcurrent = pright; pright = ptemp; } // 遍历并输出逆序后的链表 while (pcurrent != NULL) { cout << pcurrent->data << "\t"; pcurrent = pcurrent->next; } } ``` 接下来是使用栈的递归方法，这里使用Java实现。该方法首先将链表的所有元素压入栈中，然后逐个弹出栈顶元素并将其作为当前节点的`next`指针，从而实现链表的逆序。当链表不为空时，将头节点置为栈顶元素，然后继续将剩余部分的链表进行逆序。 ```java class Solution<T> { public void reverse(ListNode<T> head) { if (head == null || head.next == null) { return; } ListNode<T> currentNode = head; Stack<ListNode<T>> stack = new Stack<>(); while (currentNode != null) { stack.push(currentNode); ListNode<T> tempNode = currentNode.next; currentNode.next = null; // 断开连接 currentNode = tempNode; } head = stack.pop(); currentNode = head; while (!stack.isEmpty()) { currentNode.next = stack.pop(); currentNode = currentNode.next; } } } class ListNode<T> { T val; // 其他代码... } ``` 这两种方法都有效地实现了单向链表的逆序输出，但各有优缺点。迭代方法使用了较少的额外空间，但代码稍微复杂一些；而递归方法利用了栈的特性，代码简洁，但可能会占用更多的内存，特别是在链表非常长的情况下。在实际应用中，应根据具体需求和场景选择合适的方法。