开发者社区> 问答> 正文

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

问题:如何实现一个高效的单向链表逆序输出?
出题人:阿里巴巴出题专家:昀龙/阿里云弹性人工智能负责人

展开
收起
Runt 2020-04-14 16:32:05 2896 0
1 条回答
写回答
取消 提交回答
  • 参考答案:下面是其中一种写法,也可以有不同的写法,比如递归等。供参考。

        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;
        }
    }
    
    
    
        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;
    }
    
    2020-04-14 16:33:13
    赞同 展开评论 打赏
问答分类:
问答标签:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载