<source id="wwucw"><optgroup id="wwucw"></optgroup></source>
  • <option id="wwucw"><optgroup id="wwucw"></optgroup></option>
  • 首頁 > 試題廣場 > 從尾到頭打印鏈表
    [編程題]從尾到頭打印鏈表
    輸入一個鏈表,按鏈表值從尾到頭的順序返回一個ArrayList。
    推薦
    方法一:鏈表從尾到頭輸出,利
       查看全部
    編輯于 2015-06-18 16:53:34 回復(63)
    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 回復(208)
    有三種思路,第一就是利用棧先入后出的特性完成,第二就是存下來然后進行數組翻轉。
    第三是利用遞歸。
    
    棧思路:
    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 回復(10)
    方法一:借助堆棧的“后進先出”實現
    /**
    * ? ?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)

    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)
    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)
    啊, 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 回復(12)
    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 回復(18)
    用反向迭代器就好了
    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)
    /**
    *  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)

    上面的回答基本都是用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)
    感覺大家的代碼都有點長,我就直接一個循環解決!
    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)
    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)
    頭插法
    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)
    有點忘了 鏈表是啥了。。。
    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)
    狠狠的撸2019手机看片电影最新版