【剑指offer】从尾到头打印链表

2021年11月25日 阅读数:3
这篇文章主要向大家介绍【剑指offer】从尾到头打印链表,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

个人思路:先翻转链表,再打印。java

网上思路:利用栈的后进先出性质;或者用递归,本质也是栈。ide

 

个人代码:spa

#include <vector>
using namespace std;


struct ListNode {
       int val;
       struct ListNode *next;
       ListNode(int x) :
             val(x), next(NULL) {}
};

class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {
        if(NULL == head) return vector<int>();
        vector<int> ans;
        //先翻转
        ListNode * rh = head, * p = head->next;
        rh->next = NULL;
        while(NULL != p)
        {
            ListNode * p2 = p->next;
            p->next = rh;
            rh = p;
            p = p2;
        }
        //再打印
        p = rh;
        while(NULL != p)
        {
            ans.push_back(p->val);
            p = p->next;
        }

        return ans;
    }
};

 

网上代码:递归

方法一:借助堆栈的“后进先出”实现

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;
    }
}