Fork me on GitHub

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

问题:如何实现一个高效的单向链表逆序输出?
出题人:阿里巴巴出题专家:昀龙/阿里云弹性人工智能负责人
参考答案:下面是其中一种写法,也可以有不同的写法,比如递归等。供参考。
  1. typedef struct node{
  2. int data;
  3. struct node* next;
  4. node(int d):data(d), next(NULL){}
  5. }node;
  6. void reverse(node* head)
  7. {
  8. if(head == NULL){
  9. return;
  10. }
  11. node* pleft = NULL;
  12. node* pcurrent = head;
  13. node* pright = head->next;
  14. while(pright){
  15. pcurrent->next = pleft;
  16. node *ptemp = pright->next;
  17. pright->next = pcurrent;
  18. pleft = pcurrent;
  19. pcurrent = pright;
  20. pright = ptemp;
  21. }
  22. while(pcurrent != NULL){
  23. cout<< pcurrent->data << "\t";
  24. pcurrent = pcurrent->next;
  25. }
  26. }
  1. class Solution<T> {
  2. public void reverse(ListNode<T> head) {
  3. if (head == null || head.next == null) {
  4. return ;
  5. }
  6. ListNode<T> currentNode = head;
  7. Stack<ListNode<T>> stack = new Stack<>();
  8. while (currentNode != null) {
  9. stack.push(currentNode);
  10. ListNode<T> tempNode = currentNode.next;
  11. currentNode.next = null; // 断开连接
  12. currentNode = tempNode;
  13. }
  14. head = stack.pop();
  15. currentNode = head;
  16. while (!stack.isEmpty()) {
  17. currentNode.next = stack.pop();
  18. currentNode = currentNode.next;
  19. }
  20. }
  21. }
  22. class ListNode<T>{
  23. T val;
  24. public ListNode(T val) {
  25. this.val = val;
  26. }
  27. ListNode<T> next;
  28. }
2020-03-07 16:32:09  LeeChan 阅读(41) 评论(0) 标签:面试,01.阿里篇 分类:阿里篇