题解 | #从尾到头打印链表#做题及学习积累

从尾到头打印链表

https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        while(listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }
}

第一眼想到使用栈的数据结构

时间复杂度

  1. 遍历链表并将元素入栈:遍历整个链表的时间复杂度是 O(n),其中 n 是链表的长度。每个元素被压入栈中一次,每次操作的时间复杂度是 O(1),所以总的时间复杂度仍然是 O(n)。
  2. 从栈中弹出元素并添加到ArrayList中:每个元素从栈中弹出一次,并被添加到ArrayList中,这个过程的时间复杂度也是 O(n)。虽然ArrayList的add操作在最坏情况下可能需要扩容,但平均时间复杂度仍为 O(1),因此这一步骤的总时间复杂度为 O(n)。

综上,整个方法的时间复杂度是 O(n)+O(n)=O(n)。

空间复杂度

  1. 栈的空间占用:栈用于存储链表中的所有元素,因此其空间复杂度是 O(n)。
  2. ArrayList的空间占用:ArrayList用于存储最终的逆序列表,其空间复杂度也是 O(n)。

因为这两个数据结构是此算法中主要的空间占用者,且它们的大小都与输入的链表长度 n 线性相关,所以整个方法的空间复杂度是 O(n)+O(n)=O(n)。

他山之石,可以攻玉

题解中高赞解法使用ArrayList 中的一个方法add(index,value),这种方法的关键在于理解插入操作是如何工作的。每次调用add(0, value)时,当前列表中的所有元素都会向后移动一位,为新元素腾出位置。因此,虽然每次都是插入到0位置,但实际上每个新插入的元素都会推动前面的元素向后移,这样最先插入的元素最终会被移到列表的末尾,而最后插入的元素则会留在列表的开始位置,从而实现了逆序效果。等效实现了栈的效果。

同时,如果目标是进行覆盖型的插入,也就是说,替换掉ArrayList中指定位置的元素,而不是插入一个新元素并移动其他元素,那么应该使用set(int index, E element)方法。这个方法将指定索引位置的元素替换为新元素,并返回被替换的元素。这个操作不会改变列表的大小,只是单纯地替换元素。

全部评论

相关推荐

07-29 14:27
门头沟学院 Java
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务