大厂面试题（如何实现一个高效的单向链表逆序输出（）） _链表逆序输出

如何实现一个高效的单向链表逆序输出？
参考答案：下面是两种方式，第一种是使用while迭代循环，第二种是使用栈辅助，也可以使用递归。
第一种方式：while迭代循环，将指针的指向进行方向指向，C++代码如下：

typedef struct node{ intdata; 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; } }

【大厂面试题（如何实现一个高效的单向链表逆序输出（））】第二种方式：使用栈辅助，栈的特定是后进先出，也就是说，第一个结点先入栈，最后一个结点首先出栈，也就实现了逆序。不用栈的话就是递归，即深度优先遍历，使用一个后序遍历，即先向下递归调用，再进行打印。使用栈实现的C++代码如下：

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; public ListNode(T val) { this.val = val; } ListNode< T> next; }