抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

从头到尾打印链表

题:输入一个链表的头结点,从头到尾反过来打印出每个节点的值,链表节点定义如下:

class ListNode {
int key;
ListNode pNext;

ListNode(int key) {
this.key = key;
}
}

解法一:修改数据内容

反转链表,看是否需要,否则不推荐。

解法二:利用栈

每次将节点值存入栈,遍历完然后依次弹出,由于栈的“后进先出特点”,可以达到题目要求的效果。

代码:

private static void printListReverseIteratively(ListNode listNode) {
Stack<Integer> stack = new Stack<>();

while (listNode != null) {
stack.push(listNode.key);
listNode = listNode.pNext;
}

while (!stack.empty()) {
System.out.print(stack.pop() + " ");
}
}

解法三:递归

利用递归特性。递归到最后一个节点然后开始输出

private static void printListReverseIteratively(ListNode listNode) {
if (listNode!=null){
if (listNode.pNext!=null){
printListReverseIteratively(listNode.pNext);
}
System.out.print(listNode.key+" ");
}
}

主程序:

public static void main(String[] args) {
ListNode nodeA = new ListNode(1);
ListNode nodeB = new ListNode(2);
ListNode nodeC = new ListNode(3);
ListNode nodeD = new ListNode(4);
nodeA.pNext = nodeB;
nodeB.pNext = nodeC;
nodeC.pNext = nodeD;
printListReverseIteratively(nodeA);
}

解法三不如解法二:因为解法三当递归层级过深,可能会导致函数调用栈溢出。所以鲁棒性,解法二好过解法三。


0条评论

发表评论