题解 | #从尾到头打印链表#做题及学习积累
从尾到头打印链表
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; } }
第一眼想到使用栈的数据结构
时间复杂度
- 遍历链表并将元素入栈:遍历整个链表的时间复杂度是 O(n),其中 n 是链表的长度。每个元素被压入栈中一次,每次操作的时间复杂度是 O(1),所以总的时间复杂度仍然是 O(n)。
- 从栈中弹出元素并添加到ArrayList中:每个元素从栈中弹出一次,并被添加到ArrayList中,这个过程的时间复杂度也是 O(n)。虽然ArrayList的add操作在最坏情况下可能需要扩容,但平均时间复杂度仍为 O(1),因此这一步骤的总时间复杂度为 O(n)。
综上,整个方法的时间复杂度是 O(n)+O(n)=O(n)。
空间复杂度
- 栈的空间占用:栈用于存储链表中的所有元素,因此其空间复杂度是 O(n)。
- 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)
方法。这个方法将指定索引位置的元素替换为新元素,并返回被替换的元素。这个操作不会改变列表的大小,只是单纯地替换元素。