Java 详解如何从尾到头打印链表

Java 详解如何从尾到头打印链表

目录1.题目2.解法2.1栈2.2递归3.复杂度3.1栈3.2递归

1.http://题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

题目来源：力扣（LeetCode）

2.解法

2.1栈

栈的特点是先进后出，所以我们创建一个栈，逐个将节点压入栈内，然后建立一个数组，将栈内的节点数值逐个弹出

class Solution {

public int[] reversePrint(ListNode head) {

Stack stack = new Stack();//创建一个栈

ListNode cur = head;

//将节点压栈

while (cur != null) {

stack.push(cur);

cur = cur.next;

}

int size = stack.size();//栈的长度

int[] array = new int[size];//创建一个和栈一样长的数组

//出栈入数组

for (int i = 0; i < size; i++) {

array[i] = stack.pop().val;

}

return array;

}

}

2.2递归

public class PrintList {

ArrayList cur = new ArrayList&lkfSCOYt;Integer>();

public int[] reversePrint(ListNode head) {

recur(head);

int[] array = new int[cur.size()];

for (int i = 0; i

array[i] = cur.get(i);

}

return array;

}

public void recur(ListNode head) {

if(head == null) {

return ;

}

recur(head.next);

cur.add(head.val);

}

}

http://

3.复杂度

3.1栈

时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。 空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。

3.2递归

时间复杂度：O(n) 遍历链表，递归 NN次。

空间复杂度：O(n) 系统递归需要使用 O(N)的栈空间

array[i] = cur.get(i);

}

return array;

}

public void recur(ListNode head) {

if(head == null) {

return ;

}

recur(head.next);

cur.add(head.val);

}

}

http://

3.复杂度

3.1栈

时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。 空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。

3.2递归

时间复杂度：O(n) 遍历链表，递归 NN次。

空间复杂度：O(n) 系统递归需要使用 O(N)的栈空间

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。