归档 2015年1月

C++单链表逆置的迭代实现与递归实现

Implement the reversal of a singly linked list iteratively and recursively.

链表逆置既可以用迭代实现也可以使用递归实现。在我看来,迭代法应该比其递归形式的等价实现更加高效,内存开销更小。(试想对一个包含百万个元素的链表执行递归的逆置操作!很快栈空间就会用尽)

递归实现的代码行数更少,但是要想把代码写对会比较困难。另一方面,迭代实现代码行数较多但是比较容易验证。

1) 迭代实现:

void reverse(Node*& head) {
  if (!head) return;
  Node* prev = NULL;
  Node* curr = head;
  while (curr) {
    Node ...

继续阅读

[LeetCode]Reorder List

题目描述:

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

题目大意:

给定一个单链表L:L0→L1→…→Ln-1→Ln
重新将其排序为 ...

继续阅读

[LeetCode]Binary Tree Preorder Traversal

题目描述:

Given a binary tree, return the preorder traversal of its nodes' values.

For example:

Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

题目大意:

给定一棵二叉树,返回节点值的先序遍历结果(尽量使用非递归算法)。

解题思路:

使用数据结构栈(Stack)

先序遍历非递归算法的伪代码如下(摘自Wikipedia):

iterativePreorder(node)
  parentStack ...

继续阅读

每日归档

上个月

2014年12月

下个月

2015年2月

归档