剑指offer换空格教程(剑指offer-从尾到头打印单向链表)
链表结构如下:
class ListNode { int value ; ListNode next; public ListNode(int value) { this.value = value; } public ListNode(int value, ListNode next) { this.value = value; this.next = next; } }
解题过程:
1.看到这道题第一反应从头到尾打印链表遍历一遍链表就可以。那么从尾到头打印,势必要用栈结构实现,栈的特点先进后出。所以我们用一个辅助的栈来实现。代码如下
/** * 基于辅助空间数据结构实现 */ public static void printLinkedList(ListNode listNode) { if (listNode == null) { return; } Stack<ListNode> listNodeStack = new Stack<>(); while (listNode != null) { listNodeStack.push(listNode); listNode = listNode.next; } ListNode tmpNode; while (!listNodeStack.empty()) { tmpNode = listNodeStack.pop(); System.out.print(tmpNode.value " "); } }
2.函数调用也有一个特点,函数存放结构也是一个栈结构。
比如A函数调用B函数,B函数调用C函数,那么在栈中存储的顺序就是ABC,调用顺序就是C先调用,返回结果B调用,返回A最后调用。所以我们可以基于栈进行实现。
/** * 基于函数调用自身的栈属性实现 * @param listNode */ public static void printLinkedList1(ListNode listNode) { if (listNode == null) { return; } printLinkedList1(listNode.next); System.out.print(listNode.value " "); }
3.测试用例:
public static void main(String[] args) { ListNode node5 = new ListNode(5, null); ListNode node4 = new ListNode(4, node5); ListNode node3 = new ListNode(3, node4); ListNode node2 = new ListNode(2, node3); ListNode node1 = new ListNode(1, node2); printLinkedList(node1); System.out.println(); printLinkedList1(node1); }
结果:
,
免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com