[More] Intersection of Two Linked List

Problem

There are two singly linked lists in a system. By some programming error the end node of one of the linked list got linked into the second list, forming a inverted Y shaped list. Write a program to get the point where two linked list merge.

Image

Follow up:
Given two lists, determine if they are intersected ? In O(n) time and O(1) space, and do it in one iteration.

Algorithm

Let L1 = length of list 1, and L2 = length of list 2. Let L = min(L1, L2). Start from Lth last node of list 1 and list 2, compare each node. If node 1 == node 2, it is the first intersection of two lists. 

Code

[Leetcode] Binary Tree Maximum Path Sum

Problem

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Algorithm

Use a helper class PathSum with two fields to store the intermediate result. The startRoot stores the path sum start with root, and the crossRoot stores the path sum cross the root. Since the left subtree may have negative start wit root path sum, we need to compare it with zero when compute the max path sum start with root. 

Code

[Leetcode] Valid Number

Problem

Validate if a given string is numeric. Some examples:

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Algorithm

A valid number can contain, 0 ~ 9, at most one sign "+" or "-", at most one "." and at most "e" or "E". 

Some rules

• No "." after e
• "." must be adjacent to at least one number

[Leetcode] Binary Tree Zigzag Level Order Traversal

Problem

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Compare this problem with iterative solution of Symmetric Tree.

Code

[Leetcode] Tree Preorder, In-order and Postorder Traversal

Problem

Given a binary tree, return the preorder, in order and postorder traversal of its nodes' values.
Note: Recursive solution is trivial, could you do it iteratively ?

Algorithm

Recursive solution is easy. 

Iterative solution can be treated in a same format.

Code

[Leetcode] ZigZag Conversion

Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Algorithm

Using an array of StringBuilders to build each row. For odd column, sequentially append each letter from s to each row's string builder. For even column, do this reversely, and omit the last and first row. 

Code

[Leetcode] Word Search

Problem

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Algorithm

A simple DFS algorithm works. Use a 2D visited array to record those visited letters. 

I misunderstood the question for a long time.
"adjacent" cells are those horizontally or vertically neighboring"
For a 3*3 array, element [0,0] is not a neighbor of element [0,2]. Why I made it so completed !

Code