1. <dd id="qfst8"><pre id="qfst8"></pre></dd>
      <nav id="qfst8"><sub id="qfst8"><noframes id="qfst8"></noframes></sub></nav>
      <tbody id="qfst8"><pre id="qfst8"></pre></tbody>

      <dd id="qfst8"><track id="qfst8"></track></dd>
        1. 首頁 > 試題廣場 > 從尾到頭打印鏈表
          [編程題]從尾到頭打印鏈表
          輸入一個鏈表,按鏈表從尾到頭的順序返回一個ArrayList。
          推薦
          方法一:鏈表從尾到頭輸出,利
             查看全部
          編輯于 2015-06-18 16:53:34 回復(64)
          java 遞歸超簡潔版本
          public class Solution {
              ArrayList<Integer> arrayList=new ArrayList<Integer>();
              public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
          		if(listNode!=null){
          			this.printListFromTailToHead(listNode.next);
          			arrayList.add(listNode.val);
          		}
          		return arrayList;
              }
          }	

          編輯于 2015-08-03 00:59:00 回復(210)
          有三種思路,第一就是利用棧先入后出的特性完成,第二就是存下來然后進行數組翻轉。
          第三是利用遞歸。
          
          棧思路:
          class Solution {
          public:
          ? ? vector<int> printListFromTailToHead(ListNode* head) {
          ? ? ? ? vector<int> value;
          ? ? ? ? ListNode *p=NULL;
          ? ? ? ? p=head;
          ? ? ? ? stack<int> stk;
          ? ? ? ? while(p!=NULL){
          ? ? ? ? ? ? stk.push(p->val);
          ? ? ? ? ? ? p=p->next;
          ? ? ? ? }
          ? ? ? ? while(!stk.empty()){
          ? ? ? ? ? ? value.push_back(stk.top());
          ? ? ? ? ? ? stk.pop();
          ? ? ? ? }
          ? ? ? ? return value;
          ? ? }
          };
          
          
          數組翻轉:數組翻轉可以用C++自帶的函數,也可以自己實現
          
          class Solution {
          public:
          ? ? vector<int> printListFromTailToHead(ListNode* head) {
          ? ? ? ? vector<int> value;
          ? ? ? ? ListNode *p=NULL;
          ? ? ? ? p=head;
          ? ? ? ? while(p!=NULL){
          ? ? ? ? ? ? value.push_back(p->val);
          ? ? ? ? ? ? p=p->next;
          ? ? ? ? }
          ? ? ? ? //reverse(value.begin(),value.end()); //C++自帶的翻轉函數
          ? ? ? ? int temp=0;
          ? ? ? ? int i=0,j=value.size()-1;
          ? ? ? ? while(i<j){
          ? ? ? ? ? ? temp=value[i]; ? ?//也可以用swap函數,swap(value[i],value[j]);
          ? ? ? ? ? ? value[i]=value[j];
          ? ? ? ? ? ? value[j]=temp;
          ? ? ? ? ? ? i++;
          ? ? ? ? ? ? j--;
          ? ? ? ? }
          ? ? ? ? return value;
          ? ? }
          };
          
          遞歸思路:
          
          class Solution {
          public:
          ? ? vector<int> value;
          ? ? vector<int> printListFromTailToHead(ListNode* head) {
          ? ? ? ? ListNode *p=NULL;
          ? ? ? ? p=head;
          ? ? ? ? if(p!=NULL){
          ? ? ? ? ? ? if(p->next!=NULL){
          ? ? ? ? ? ? ? ? printListFromTailToHead(p->next);
          ? ? ? ? ? ? }
          ? ? ? ? ? ? value.push_back(p->val);
          ? ? ? ? }
          ? ? ? ? return value;
          ? ? }
          };
          
          

          編輯于 2018-03-01 16:14:12 回復(14)

          python版遞歸法,只有3行代碼

          # -*- coding:utf-8 -*-
          # class ListNode:
          #     def __init__(self, x):
          #         self.val = x
          #         self.next = None
          class Solution:  
          # 返回從尾部到頭部的列表值序列,例如[1,2,3]  
              def printListFromTailToHead(self, listNode):  
              # write code here  
              if listNode is None:  
                  return []  
              return self.printListFromTailToHead(listNode.next) + [listNode.val]
          編輯于 2017-12-24 22:29:56 回復(27)
          方法一:借助堆棧的“后進先出”實現
          /**
          * ? ?public class ListNode {
          * ? ? ? ?int val;
          * ? ? ? ?ListNode next = null;
          *
          * ? ? ? ?ListNode(int val) {
          * ? ? ? ? ? ?this.val = val;
          * ? ? ? ?}
          * ? ?}
          *
          */
          import java.util.ArrayList;
          import java.util.Stack;
          public class Solution {
          ? ? public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
          ? ? ? ? Stack<Integer> stack=new Stack<Integer>();
          ? ? ? ? while(listNode!=null){
          ? ? ? ? ? ? stack.push(listNode.val);
          ? ? ? ? ? ? listNode=listNode.next; ? ??
          ? ? ? ? }
          ? ? ????
          ? ? ? ? ArrayList<Integer> list=new ArrayList<Integer>();
          ? ? ? ? while(!stack.isEmpty()){
          ? ? ? ? ? ? list.add(stack.pop());
          ? ? ? ? }
          ? ? ? ? return list;
          ? ? }
          }


          方法二:借助遞歸實現(遞歸的本質還是使用了堆棧結構)
          import java.util.ArrayList;
          import java.util.Stack;
          public class Solution {
          ? ? public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
          ? ? ? ? ArrayList<Integer> list=new ArrayList<Integer>();
          ? ? ? ??
          ? ? ? ? ListNode pNode=listNode;
          ? ? ? ? if(pNode!=null){
          ? ? ? ? ? ? if(pNode.next!=null){
          ? ? ? ? ? ? ? ? list=printListFromTailToHead(pNode.next);
          ? ? ? ? ? ? }
          ? ? ? ? ? ? list.add(pNode.val);
          ? ? ? ? }
          ? ? ? ??
          ? ? ? ? return list;
          ? ? }
          }

          發表于 2015-05-30 19:56:54 回復(39)
          啊, Javascript 沒人權啦
          /*function ListNode(x) {
          ? ? this.val = x;
          ? ? this.next = null;
          }*/
          function printListFromTailToHead(head) {
          ? ? // write code here
          ? ? var res = [], pNode = head;
          ? ? while (pNode != null) {
          ? ? ? ? res.unshift(pNode.val);
          ? ? ? ? pNode = pNode.next;
          ? ? }
          ? ? return res;
          }
          
          編輯于 2017-09-20 12:29:04 回復(13)
          C++版,遞歸
          class Solution {
           public:
            vector<int> dev;
            vector<int>& printListFromTailToHead(struct ListNode* head) {
              if(head!=NULL) {
                if(head->next!=NULL) {
                  dev=printListFromTailToHead(head->next);
                }
                dev.push_back(head->val);
              }
              return dev;
            }
          };

          編輯于 2017-05-11 00:29:35 回復(15)
          import java.util.ArrayList;
          import java.util.Collections;
          public class Solution {
              public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
                  ArrayList<Integer> list = new ArrayList<Integer>();
                  
                  while(listNode != null){
                      list.add(listNode.val);
                      listNode = listNode.next;
                  }
                  
                  Collections.reverse(list);//使用Collections的reverse方法,直接將list反轉
                  return list;
              }
          }

          發表于 2016-09-14 13:56:30 回復(21)
          用反向迭代器就好了
          class Solution {
          public:
              vector<int> printListFromTailToHead(struct ListNode* head) {
                  vector<int> v;
                                 
                  ListNode *p = head;
                  while (p != nullptr) {
                     v.push_back(p->val);
                     p = p->next;
                  }
                  //反向迭代器創建臨時對象
                  return vector<int>(v.rbegin(), v.rend());
              }
          };

          發表于 2016-08-01 11:18:51 回復(14)
          # -*- coding:utf-8-*-
          #?classListNode:
          #???? def __init__(self, x):
          #???????? self.val = x
          #???????? self.next = None
          ?
          classSolution:
          ????# 返回從尾部到頭部的列表值序列,例如[1,2,3]
          ????def printListFromTailToHead(self, listNode):
          ????????# write code here
          ????????result = []
          ????????iflistNode is None:
          ????????????returnresult
          ?????????????
          ????????whilelistNode.next is not None:
          ????????????result.extend([listNode.val])
          ????????????listNode=listNode.next
          ????????result.extend([listNode.val])
          ?????????
          ????????returnresult[::-1]

          發表于 2016-03-20 23:17:20 回復(15)
          最佳代碼:代碼思路借助棧,遍歷的時候入棧,由于數據結構中棧的特點是先進后出,所以遍歷的過程中壓棧,推棧,完了彈棧加到ArrayList中。有兩個容易出錯的地方:第一,第一次測試用例,{}返回[ ],null是null,而[ ]是new ArrayList()但是沒有數據。第二,遍歷stack用的方法是!stak.isEmpty()方法,而不是for循環size遍歷。。
          /**
          * ? ?public class ListNode {
          * ? ? ? ?int val;
          * ? ? ? ?ListNode next = null;
          *
          * ? ? ? ?ListNode(int val) {
          * ? ? ? ? ? ?this.val = val;
          * ? ? ? ?}
          * ? ?}
          *
          */
          import java.util.Stack;
          import java.util.ArrayList;
          public class Solution {
          ? ? public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
          ? ? ? ? if(listNode == null){
          ? ? ? ? ? ? ArrayList list = new ArrayList();
          ? ? ? ? ? ? return list;
          ? ? ? ? }
          ? ? ? ? Stack<Integer> stk = new Stack<Integer>();
          ? ? ? ? while(listNode != null){
          ? ? ? ? ? ? stk.push(listNode.val);
          ? ? ? ? ? ? listNode = listNode.next;
          ? ? ? ? }
          ? ? ? ? ArrayList<Integer> arr = new ArrayList<Integer>();
          ? ? ? ? while(!stk.isEmpty()){
          ? ? ? ? ? ? arr.add(stk.pop());
          ? ? ? ? }
          ? ? ? ? return arr;
          ? ? }
          }
          編輯于 2015-08-24 18:00:57 回復(15)

          上面的回答基本都是用java或者c實現的,是欺負我javascript沒人嗎?
          這道題實現起來比較簡單,就是鏈表的逆序打印。

          /*function ListNode(x){
              this.val = x;        // 節點的數據域
              this.next = null;    // 節點指針域,通過this.next使指針后移
          }*/
          function printListFromTailToHead(head)
          {
              var arr = [];    // 創建一個空數組,將每個節點存放哎數組中
              if(!head) {        // 判斷鏈表是否為空
                  return arr;
              }
              while(head) {
                  arr.unshift(head.val);    // 使用unshift()方法,將當前節點放到數組的開頭
                  head = head.next;    // 指針后移
              }
          
              return arr;    
          }
          
          發表于 2017-05-25 23:03:00 回復(3)
          /**
          *  struct ListNode {
          *        int val;
          *        struct ListNode *next;
          *        ListNode(int x) :
          *              val(x), next(NULL) {
          *        }
          *  };
          */
          class Solution {
          public:
              vector<int> printListFromTailToHead(struct ListNode* head) {
          //利用棧的逆序輸出特性    	
                  stack<int> stack;
                  vector<int> vector;
                  struct ListNode *p = head;
                  if (head != NULL) {
                  	stack.push(p->val);
                      while((p=p->next) != NULL) {
                      	stack.push(p->val);
                  	}
                      while(!stack.empty()) {
                          vector.push_back(stack.top());
                          stack.pop();
                  	}
                  }
                  return vector;
              }
                  
          };

          發表于 2015-10-16 10:57:59 回復(9)
          感覺大家的代碼都有點長,我就直接一個循環解決!
          vector<int> printListFromTailToHead(struct ListNode* head) {
                  vector<int> v;
                  while(head != NULL)
                  {
                      v.insert(v.begin(),head->val);
                      head = head->next;
                  }
                  return v;
              }

          發表于 2015-08-22 20:51:35 回復(15)
          # python的實現這么少, 我來添磚加瓦
          # 1.先遍歷鏈表元素到棧
          # 2.棧再彈出
          

          # -*- coding:utf-8 -*- # class ListNode: #???? def __init__(self, x): #???????? self.val = x #???????? self.next = None class Solution: ??? # 返回從尾部到頭部的列表值序列,例如[1,2,3] ??? def printListFromTailToHead(self, listNode): ??????? # write code here ??????? lst,lst_bak = [],[] ??????? if not listNode: ??????????? return lst ??????? while listNode: ??????????? lst.append(listNode.val) ??????????? listNode = listNode.next ??????? while lst: ??????????? lst_bak.append(lst.pop()) ??????? return lst_bak

          編輯于 2018-01-29 15:00:53 回復(6)
          import java.util.ArrayList;
          public class Solution {
              public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
                  ArrayList<Integer> list = new ArrayList<Integer>();
                  if(listNode==null)
                      return list;
                  get(listNode, list);
                  return list;
              }
          	public void get(ListNode listNode,ArrayList<Integer> list){
          		if(listNode.next==null){
          			list.add(listNode.val);
          			return;
          		}
          		get(listNode.next, list);
          		list.add(listNode.val);
          	}
          }

          發表于 2016-04-14 20:40:37 回復(1)
          Exe頭像 Exe
          利用頭插arraylist實現棧的功能
          ?public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
          ? ? ? ? ArrayList<Integer> list = new ArrayList<Integer>();
          ? ?if(listNode == null)
          ? ?return list;
          ? ?while(listNode.next != null){
          list.add(0,listNode.val);
          listNode = listNode.next;
          }
          list.add(0,listNode.val);
          return list;
          ? ? }

          發表于 2015-09-01 12:15:04 回復(5)
          public class LinkedList {
          	public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
                  ListNode list = new ListNode(0);
                  
                  ListNode cursor = listNode;
                  ListNode top = list;
                 
                  
                  ArrayList<Integer> result = new ArrayList<Integer>();
                  while(cursor!=null){
                  	   ListNode temp = new ListNode(cursor.val);
                         temp.next = top;
                         top = temp;
                         cursor = cursor.next;
                  }
                  
                  while(top!=null){
               		result.add(top.val);      
                      top = top.next;
                  }
                  result.remove(result.size()-1);
                  
                return result;
               
              }
          
          }

          編輯于 2015-08-06 16:04:52 回復(3)
          頭插法
          add()有這個兩個參數的方法。
          import java.util.ArrayList;
          public class Solution {
          ? ? public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
          ? ? ? ? ArrayList<Integer> list = new ArrayList<Integer>();
          ? ? ? ? while(listNode != null) {
          ? ? ? ? ? ? list.add(0, listNode.val);
          ? ? ? ? ? ? listNode = listNode.next;
          ? ? ? ? }
          ? ? ? ? return list;
          ? ? }
          }
          

          發表于 2018-05-05 16:26:36 回復(3)
          import java.util.ArrayList;
          import java.util.Stack;
          public class Solution {
          ? ? public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
          
           Stack<ListNode> stack = new Stack<ListNode>();
           ArrayList<Integer> list=new ArrayList<Integer>();
           ListNode current=listNode;
           while(current!=null){
           stack.push(current);
           current=current.next;
           }
           while(!stack.isEmpty()){
           list.add(new Integer(stack.pop().val));
           }
           
           return list;
          
           }
          }
          

          發表于 2015-04-09 20:55:24 回復(3)
          有點忘了 鏈表是啥了。。。
          public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
          ? ? ? ? ArrayList<Integer> list = new ArrayList<>();
          ? ? ? ? for(;listNode != null;) {
          ? ? ? ? ? ? list.add(0, listNode.val);
          ? ? ? ? ? ? listNode = listNode.next;
          ? ? ? ? }
          ? ? ? ? return list;
          ? ? }

          發表于 2017-09-04 13:49:53 回復(0)
          微拍福利