剑指offer——从尾到头打印链表

vampire 2020年10月22日 51次浏览
  • 题目链接: 从尾到头打印链表

    题目描述
    输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
    提示
    以下方法都是针对不带头结点,如有问题,欢迎指正。

  • 思路1

    我们知道栈是有后进先出特性的,所以遍历链表,将链表元素值入栈,然后将栈中元素弹出到目标ArrayList;

    	class Solution {
    	public:
    	vector<int> printListFromTailToHead(ListNode* head) {
    	        stack<int> s;
    	        vector<int> result;
    	        while(head!=NULL){
    	            s.push(head->val);
    	            head = head->next;
    	        }
    	        while(!s.empty()){
    	            result.push_back(s.top());
    	            s.pop();
    	        }
    	        return result;
    	    }
    	};
    
  • 思路2

    我们可以利用递归的思想来遍历,借鉴之后的二叉树递归遍历

    	class Solution {
    	public:
    	    vector<int> printListFromTailToHead(ListNode* head) {
    	        vector <int> result;
    	        if(head==nullptr){
    	            return result;
    	        }
    	        result = printListFromTailToHead(head->next);
    	        result.push_back(head->val)
    	        return result;
    	    }
    	};
    
  • 思路3

    我们直接将链表用头插法逆置,然后遍历

    	class Solution {
    	public:
    	    vector<int> printListFromTailToHead(ListNode* head) {
    	        vector<int> result;
    	        ListNode* p = head;
    	        head = nullptr;
    	        while(p!=nullptr){
    	            ListNode* tmp = p->next;
    	            p->next = head;
    	            head = p;
    	            p = tmp;
    	        }
    	        while(head!=nullptr){
    	            result.push_back(head->val);
    	            head = head->next;
    	        }
    	        return result;
    	    }
    	};
    
    
  • 思路4

    与思路3不同之处在于链表逆置的方法不不同,通过双指针来逆置

    	class Solution {
    	public:
    	    vector<int> printListFromTailToHead(ListNode* head) {
    	        ListNode* pre = nullptr;
    	        ListNode* cur = head;
    	        ListNode* tmp = head;
    	        while(cur!=nullptr){
    	            tmp = cur->next;
    	            cur->next = pre;
    	            pre = cur;
    	            cur = tmp;
    	        }
    	        vector<int> result;
    	        while(pre != nullptr){
    	            result.push_back(pre->val);
    	            pre = pre->next;
    	        }
    	        return result;
    	    }
    	};