Linked List Cycle Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space? tag: two pointers, linked-list 很巧妙的一道题。最暴力的解法，给访问过的node做一个标记，如果新访问的node已经被标记为已访问的话，则存在环。否则如果node的next为null的话，不存在环。但是需要线性额外空间。 本题我们可以用双指针算法。 定义一个fast指针，每次移动两个node。定义一个slow指针，每次移动一个node。 假设存在环，当slow指针进入环的第一个节点时，fast指针已经在环里绕了一圈或多圈了。 这是，如果以slow指针为相对参考坐标系（上点高中物理的知识），那么slow指针静止不动，fast指针每次以一个node的速度接近slow指针。这样两个指针必定会相遇。证明存在环。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; […]

Best Time to Buy and Sell Stock III Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple […]

Reverse Linked List II 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 ≤ n ≤ length of list. tag: […]

Binary Tree Inorder Traversal Given a binary tree, return the inorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively? confused what “{1,#,2,3}” means? > read more on how binary tree […]

Valid Palindrome Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, “A man, a plan, a canal: Panama” is a palindrome. “race a car” is not a palindrome. Note: Have you consider that the string might be empty? This is a […]

Copy List with Random Pointer A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. tag: hashtable, linked-list 虽然被标记为hard，但代码不长。 问题关键是，在拷贝完next指针后，要根据原来链表中的random的地址，找到新建的链表中对应的node的地址，这里我们用一个hashtable来实现，在拷贝next指针时，将对应关系记录下来。 空间复杂度o(n)，时间复杂度o(n)。 /** * Definition for singly-linked list with […]

Divide Two Integers Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT. tags: math, binary search 8/10/2015 update Reference http://yucoding.blogspot.com/2013/01/leetcode-question-28-divide-two-integers.html class Solution { public: int divide(int dividend, int divisor) { int flag = 1; long ldividend = dividend; long ldivisor = divisor; if(ldividend […]

Remove Element Given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesn’t matter what you leave beyond the new length. 简单题，与上一题Remove Element in Sorted Array类似 class Solution { public: int removeElement(int A[], […]