36. 两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
思路：将两个链表遍历至末尾分别存储到两个栈内，此时栈顶为链表尾结点。若两个链表有公共结点，则其公共结点之后的尾部结点均是公用的，因此我们从尾部开始比较，遇到不同结点，则返回上一个相同结点，该结点必为第一个公共结点。
另一种思路是，得出两个链表的长度差值，令长的先走差值步，再同时开始遍历，遍历至相同结点，则返回；这种解法，在网上有更简洁的写法，可以不统计长度，直接开始遍历两个链表，若ptr1将链表1走完，那么就开始去走链表2，ptr2将链表2走完，就去走链表1。如此若两链表长度相同，则走第一遍就能得到第一个公共结点，若长度不相等，加入则当ptr1走完链表1之后去到另一个链表的头部继续遍历，此时和ptr2之间的距离就是两个链表的长度差，那么之后再遇到相同结点，就一定是第一个公共结点了。这要比第一种方法代码上相对简洁。
解法一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
import java.util.Stack;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
Stack<ListNode> s1 = new Stack<ListNode>();
Stack<ListNode> s2 = new Stack<ListNode>();
ListNode ptr1 = pHead1, ptr2 = pHead2;
while(ptr1!=null){
s1.push(ptr1);
ptr1 = ptr1.next;
}
while(ptr2!=null){
s2.push(ptr2);
ptr2 = ptr2.next;
}
ListNode res = null;
while(!s1.isEmpty() && !s2.isEmpty()){
if(s1.peek() == s2.peek()){
res = s1.pop();
s2.pop();
}
else if(s1.peek() != s2.peek()) return res;
if(s1.isEmpty() || s2.isEmpty()) return res;
}
return null;
}
}
解法二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
import java.util.Stack;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode ptr1 = pHead1, ptr2 = pHead2;
while(ptr1!=ptr2){
ptr1 = (ptr1 == null)? pHead2:ptr1.next;
ptr2 = (ptr2 == null)? pHead1:ptr2.next;
}
return ptr1;
}
}
37. 第一个只出现一次的字符
统计一个数字在排序数组中出现的次数。
思路： 一般情况直接遍历肯定能找到答案，且复杂度为O(n)，但是面试这样肯定过不了。这题注意是有序数组，那么肯定先想到二分，但是二分找到这个数对于统计它的次数是无益的，因而我们需要改写二分，改成找到左边界和右边界。普通情况下和普通二分一样，但是当mid==k时候，假如我们要找左侧第一个k，那么此时需要判断mid-1是否为k，若为k则左侧边界肯定在mid左侧，那么使end = end - 1，同理右侧也是如此。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.HashMap;
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int left = getFirst(array, k, 0, array.length - 1);
int right = getLast(array, k, 0, array.length - 1);
return right - left + 1;
}
public int getFirst(int[] array, int k,int start, int end){
int mid = (start + end) / 2;
while(start <= end){
if(array[mid] > k) end = mid - 1;
else if(array[mid] < k) start = mid + 1;
else if(mid > 0 && array[mid - 1] == k) end = mid - 1;
else return mid;
mid = (start + end) / 2;
}
return start;
}
public int getLast(int[] array, int k, int start, int end){
int mid = (start + end) / 2;
while(start <= end){
if(array[mid] > k) end = mid - 1;
else if(array[mid] < k) start = mid + 1;
else if(mid + 1 <= end && array[mid+1] == k) start = mid + 1;
else return mid;
mid = (start + end) / 2;
}
return end;
}
}
38. 二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路： 递归遍历即可，根据题目定义的深度，即该数的深度等于最长路径，也就等于左子树或者右子树的较大者加1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
}
}
39. 平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
思路： 根据平衡二叉树定义，根结点左右子树深度差小于1，且左右子树均为平衡二叉树。写一个递归返回子树长度，若左右子树高度差有超过1，则将flag标记为false即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
private boolean isBalanced=true;
public boolean IsBalanced_Solution(TreeNode root) {
int depth = countDepth(root);
return isBalanced;
}
public int countDepth(TreeNode root){
if(root == null || isBalanced == false) return 0;
int left = countDepth(root.left);
int right = countDepth(root.right);
if(Math.abs(left - right) > 1) isBalanced=false;
return left > right? left + 1: right + 1;
}
}