# 数据结构算法回顾

``` 今天发现自己对于数据结构有点陌生了，最近几年主要精力放在语言层次上，这些基本的东西反而有些陌生了，温故而知新，决定花些时间把这些东西整理下。本文不定期更新。 - 树的层次遍历 输入 4 / 6 9 / 7 8 12 要求打印出 4->6->9->7->8->12 public void PrintByLevel() { LinkedList<Tree> l = new LinkedList<Tree>(); l.add(this); while (!l.isEmpty()) { Tree tmp = l.pollFirst(); System.out.println(tmp.getValue()); if (null != tmp.getLChild()) { l.add(tmp.getLChild()); } if (null != tmp.getRChild()) { l.add(tmp.getRChild()); } } } 链表的递归和非递归反转 递归反转 // 递归，在反转当前节点之前先反转后续节点 public static ListNode Reverse(ListNode head) { if (null == head || null == head.next) { return head; } ListNode reversedHead = Reverse(head.next); head.next.next = head; head.next = null; return reversedHead; } 非递归反转 public static ListNode NoneRecursiveReverse(ListNode head) { ListNode retval = null; ListNode node = head; ListNode preNode = null; while ( node != null ){ // get the next node, and save it at pNext ListNode nextNode = node.next; // if the next node is null, the current is the end of original // list, and it's the head of the reversed list if ( nextNode == null) { retval = node; } // reverse the linkage between nodes node.next = preNode; preNode = node; node = nextNode; } return retval; } ```