从尾到头打印链表
<h2 id="题目描述">题目描述</h2><p>输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。</p>
<p>如输入{1,2,3}的链表如下图:</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202502231440308.png" alt="" loading="lazy"></p>
<p>返回一个数组为</p>
<p>0 <= 链表长度 <= 10000</p>
<p>示例1</p>
<p>输入：</p>
<pre><code>{1,2,3}
</code></pre>
<p>返回值：</p>
<pre><code>
</code></pre>
<p>示例2</p>
<p>输入：</p>
<pre><code>{67,0,24,58}
</code></pre>
<p>返回值：</p>
<pre><code>
</code></pre>
<h2 id="思路及解答">思路及解答</h2>
<p>⾸先我们需要想⽤哪些解法可以解，⼤概有如下：</p>
<ul>
<li>使⽤栈</li>
<li>使⽤递归调⽤</li>
<li>头插法</li>
</ul>
<h3 id="借助栈实现">借助栈实现</h3>
<p>先把元素⾥⾯的元素从头到尾遍历取出放在栈⾥⾯，然后再把栈的元素去出来放在ArraList ⾥⾯。主要利⽤了栈的先进后出的规则，这样就可以实现倒序的功能。Java 代码实现如下：</p>
<pre><code class="language-java">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;
}
}
</code></pre>
<h3 id="递归调">递归调⽤</h3>
<p>前⾯我们能想到栈，那么我们何必⾃⼰实现呢？其实⽅法的调⽤过程，就是⼀个天然的栈调⽤的过程呀，只需要判断当前节点是不是为空，为空则不输出，不为空则递归下⼀个节点，对下⼀个节点处理之后，把结果使⽤ArrayList.addAll() 加到结果中，再把⾃身加到结果中即可：</p>
<pre><code class="language-java">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;
}
}
</code></pre>
<h3 id="头插法">头插法</h3>
<p>遍历每⼀个节点，然后把它插⼊到头部，这样⼀直遍历到尾的时候，就相当于将整个链表都反转⼀遍了，然后再从头到尾遍历放到ArryList 即可。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202502231443624.png" alt="" loading="lazy"></p>
<pre><code class="language-java">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;
}
}
</code></pre>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/18894404
頁:
[1]