标签归档：leetcode

Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.

不得不承认这道题目解决起来非常的巧妙。像大多数难题一样，需要经过非常巧妙的观察才可以用简洁的方式求解。

朴素解法, O(m+n):

将两个数组进行合并，然后寻找第k小的元素可能非常直观。合并操作需要花费额外的O(m + n)的空间。线性运行时间已经很好了，但我们还能再做一些优化吗？

朴素解法的优化, ...

题目描述：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], ...

题目描述：

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ...

题目描述：

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
重新将其排序为： L0→Ln→L1→Ln-1→L2→Ln-2→…

必须在不改变节点值的前提下就地完成链表的顺序重排。

解题思路：

1. 利用快慢指针找到链表中点mid，将链表分为左右两半
2. 将链表的右半部分就地逆置 ...

题目描述：

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 = empty stack
  while (not parentStack.isEmpty() or ...