剑指Offer(3)--从尾到头打印链表

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


文章目录


题目描述

输入一个链表,按链表从尾到头的顺序返回一个ArrayList。html

思路以及解法

????‍♂️????‍♂️首先咱们须要想用哪些解法能够接,大概有以下:java

  • 使用栈
  • 使用递归调用
  • 头插法

借助栈实现

先把元素里面的元素从头至尾遍历取出放在栈里面,而后再把栈的元素去出来放在ArraList里面。主要利用了栈的先进后出的规则,这样就能够实现倒序的功能。show you the code:node

/**
*    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<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> results = new ArrayList<>();
        while (!stack.isEmpty()) {
            results.add(stack.pop()); 
        }
        return results;
    }}

递归调用

前面咱们能想到栈,那么咱们何须本身实现呢?其实方法的调用过程,就是一个自然的栈调用的过程呀,只须要判断当前节点是否是为空,为空则不输出,不为空则递归下一个节点,对下一个节点处理以后,把结果使用ArrayList.addAll()加到结果中,再把自身加到结果中,emmmmm有道理,说码就码:ide

/**
*    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) {
        ArrayList<Integer> results = new ArrayList<>();
        if(listNode!=null){
            // 对后面的元素进行处理
            results.addAll(printListFromTailToHead(listNode.next));
            // 最后添加自身
            results.add(listNode.val);
        }
        return results;
    }}

头插法

意思是,咱们遍历每个节点,而后把它插入到头部,这样一直遍历到尾的时候,就至关于将整个链表都反转一遍了,而后再从头至尾遍历放到ArryList便可。
剑指Offer(3)--从尾到头打印链表_剑指Offer学习

import java.util.ArrayList;import java.util.Stack;public class Solution {
    public  ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode head = new ListNode(-1);
        while(listNode!=null){
            // 先把当前node的next保存起来
            ListNode temp = listNode.next;
            // 把当前节点的next指针指向head的下一个节点
            listNode.next = head.next;
            // 把head的next指向当前节点
            head.next = listNode;
            // 将遍历的指针指向了遍历的下一个元素
            listNode = temp;
        }
        ArrayList<Integer> results = new ArrayList<>();
        head = head.next;
        // 遍历输出
        while(head!=null){
            results.add(head.val);
            head = head.next;
        }
        return results;
    }}

此文章仅表明本身(本菜鸟)学习积累记录,或者学习笔记,若有侵权,请联系做者删除。人无完人,文章也同样,文笔稚嫩,在下不才,勿喷,若是有错误之处,还望指出,感激涕零~this

技术之路不在一时,山高水长,纵使缓慢,驰而不息。指针

公众号:秦怀杂货店code

剑指Offer(3)--从尾到头打印链表_剑指Offer_02