剑指 Offer 06. 从尾到头打印链表
这道题目比较简单,两种解题方法都是可以想出来的,代码部分就没有写注释哦,水一道题目😋
题目
输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例 1:
输入:head = [1,3,2]
输出:[2,3,1]
限制:
0 <= 链表长度 <= 10000
解题方法一
/**
* 首先遍历链表得到长度,然后创建一定长度数组,最后再次遍历链表,同时将节点存入数组 数组从后往前存放
* 注意 链表为空返回的是[] 而不是null
* @param head
* @return
*/
public int[] reversePrint(ListNode head) {
// TMD 如果为空返回[]!!
// if (head == null){
// return null;
// }
int listLen = 0;
ListNode cur = head;
while (cur != null){
listLen++;
cur = cur.next;
}
int[] resultArr = new int[listLen];
for (int i = listLen - 1; i >=0 ; i--) {
resultArr[i] = head.val;
head = head.next;
}
return resultArr;
}
解题方法二
/**
* 使用栈结构 先进后出特点 依次压栈然后依次弹栈存放数组中
* 时间复杂度:O(n)。正向遍历一遍链表,然后从栈弹出全部节点,等于又反向遍历一遍链表。
* 空间复杂度:O(n)。额外使用一个栈存储链表中的每个节点。
*
* @param head
* @return
*/
public int[] reversePrint2(ListNode head) {
Stack<Integer> stack = new Stack<>();
while (head != null){
stack.add(head.val);
head = head.next;
}
int[] resultArray = new int[stack.size()];
for (int i = 0; i < resultArray.length; i++) {
resultArray[i] = stack.pop();
}
return resultArray;
}
微信关注
阅读剩余
版权声明:
作者:理想
链接:https://www.imyjs.cn/archives/552
文章版权归作者所有,未经允许请勿转载。
THE END