Linked List

237  Delete Node in a Linked List

题目：Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list -- head = [4,5,1,9]

删除给定节点。

思路：直接给被删除的节点，可以直接将该指针的值指向下一个节点。

19 Remove Nth Node From End of List

题目：Given a linked list, remove the n-th node from the end of list and return its head.

对于给定的链表，删除第n个节点。

思路：采用双指针，让一个先走n步，然后两个一起前进至链表末端，则另一个停在第n个节点，然后执行相应的删除操作。

206 Reverse Linked List

题目：Reverse a singly linked list.

将链表反转。

思路：新建一个链表，并将传入链表的值不断地往头结点插入。

21 Merge Two Sorted Lists

题目：Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

将两个有序链表合并

思路：从头往后，将两链表的值比较并存入新的链表指针中，只剩一个链表时可以直接将链表接在新链表后面。

234 Palindrome Linked List

题目：Given a singly linked list, determine if it is a palindrome.

根据已给的链表，判断其是否为回文链表

思路：进行对称判断相应指针的值是否一样，对于链表老说可以采用双指针，一快一慢，一个走到中间时，将后面部分的链表内容翻转传回，并跟链表前部分进行对比。

141 Linked List Cycle

题目：Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

根据已给的链表，判断其是否为循环链表。

解法：采用双指针，一个快一个慢，若两个指针指向的地址一样，则为循环链表。

---

Trees

104 Maximum Depth of Binary Tree

题目：Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note:A leaf is a node with no children.

根据已给的树，返回该树的最大深度

解法：深度优先方法，采用递归求解；广度优先方法，采用队列方法。

98 Validate Binary Search Tree

题目：Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.

The right subtree of a node contains only nodes with keys greater than the node's key.

Both the left and right subtrees must also be binary search trees.

给一棵二叉查找树，判断其对否有效。

解法：判断左子树是否比父节点小，右子树是否比父节点大。采用递归求解，针对每一节点传入该节点的最大最小限制值。

101 Symmetric Tree

题目：Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

判断一棵树是否镜像。

思路：自己没解出来，网上大神的做法是使用queue，缓存每一层的节点，根据镜像原则在缓存的时候左右子树的缓存顺序是不一样的。左子树是left->left,left->right；右子树是right->right,right->left的顺序，这样就保证左右两个子树缓存的节点是镜像的，便于后续的值判断。

102 Binary Tree Level Order Traversal

题目：Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

按层输出数左右元素。

思路：输出元素的缓存使用vector<vector<int>>，对于每一层元素不同导致不能直接事先定义矩阵的大小。可以每一层定一个变量vector<int>，每一层元素处理完就push_back()到输出缓存变量中。

对于元素的提取，需要使用到queue，每处理一层节点。就把下一层节点指针缓存到queue中，直至没有节点。

108 Convert Sorted Array to Binary Search Tree

题目：Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

将有序向量转化成一个二分查找树。

思路：使用二分查找的方法，采用递归形式折半处理为一个树，为加快整个运行效率，可以使用iter，省去传递数组时的构造时间以及空间。

---

Sorting and Searching

88 Merge Sorted Array

题目：Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.

You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

将两个有序向量合并。

思路：对于有序向量合并问题，应从后往前处理，这样就可以保证每次处理的都是最大值，比较方便一个loop完成整个向量的合并问题。