个性化阅读
专注于IT技术分析

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

如何实现一个高效的单向链表逆序输出?

参考答案:下面是两种方式,第一种是使用while迭代循环,第二种是使用栈辅助,也可以使用递归。

第一种方式:while迭代循环,将指针的指向进行方向指向,C++代码如下:

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;
    }
}

第二种方式:使用栈辅助,栈的特定是后进先出,也就是说,第一个结点先入栈,最后一个结点首先出栈,也就实现了逆序。不用栈的话就是递归,即深度优先遍历,使用一个后序遍历,即先向下递归调用,再进行打印。使用栈实现的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;
}
赞(0) 打赏
未经允许不得转载:srcmini » 大厂面试题:如何实现一个高效的单向链表逆序输出?
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏