Linked List Cycle II Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Follow up: Can you solve it without using extra space? 与上一题类似，这里我直接复用并修改了上一题的代码。 我们这样来想： 设置两个指针fast和slow，fast指针每次走2步，slow指针每次走1步。 假设进入环之前的路径长为n，环的长度为m。那么当slow指针进入环的第一个节点时，slow指针走了n步，fast指针在环里走了n步。两个指针的距离为m-n步。slow指针每走1步，fast指针都会追近1步。那么，当slow指针走了m-n步时，两个指针相遇。此时，fast-slow指针距离下次抵达环入口的距离为n步。 在fast-slow指针相遇时，在链表入口处放置一个指针p，p指针每次走一步。slow指针也每次走一步。这样当slow和p都再走n步时，两者在环的入口处相遇。即返回结果。 /** * Definition for singly-linked list. * struct ListNode { * int val; […]

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[], […]