Leetcode HOT 100

文章是为了记录hot100思路，为了面试

160.相交链表

解题思路：

首先由题中已给信息，可知，链表A和链表B均不为空链表，其次假设链表A和链表B的首个公共节点是node节点，其中链表A中总的节点数是a，链表B的节点总数是b，从首个公共节点到链表结尾的节点数目是c。

链表A的头节点headA，链表B的头节点headB，此处我们引入俩个指针，指针A先遍历链表A再遍历链表B，直到首个公共节点；同理指针B先遍历链表B，再遍历链表A，直到首个公共节点。

其中指针A走过的步数是：

a+(b-c)

其中指针B走过的步数是：

b+(a-c)

由上可知，

a+(b-c)=b+(a-c)

若c=0，则说明链表A，链表B之间不存在公共节点，此时指针A、B均指向null；

反之，指针A、B同时指向第一个公共节点node。

C++

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *A = headA; ListNode *B = headB; while(A != B) { A = A != nullptr ? A = A->next : headB; B = B != nullptr ? B = B -> next : headA; } return A; } };

python

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def getIntersectionNode(self, headA, headB): """ :type head1, head1: ListNode :rtype: ListNode """ A,B = headA, headB while A!= B: A = A.next if A else headB B = B.next if B else headA return A

236.二叉树的最近公共祖先

由题意可知，若root是节点p、节点q的最近公共祖先，那么应该是以下几种情况之一：

①节点p、节点q在root的左右子树当中；

②p=root，节点q在root的左右子树当中；

③q=root，节点p在root的左右子树当中；

那么我们考虑使用递归来处理这个问题，其中对于链表的遍历，我们采用先序遍历。

遇到节点p、节点q时返回当前的root；

由底至顶进行回溯，当节点p/节点q位于root的左右子树中时，节点root就是最近公共祖先，则向上返回root。

终止条件：

当root越过叶子节点，直接返回null；

当root等于p/q，直接返回root；

递归条件

递归root的左子树，返回值记为left；

递归root的右子树，返回值记为right；

返回值

根据left以及right的值进行判断，有以下4种情况：

· left==NULL and right==null

说明root的左右子树当中都不存在p、q，返回null；

· left==NULL and right !=null

说明root的左子树当中不存在节点p/q，右子树当中存在节点p/q，返回right

· left!=NULL and right ==null

说明root的左子树当中存在节点p/q，右子树当中不存在节点p/q，返回left

· left!=NULL and right!=null

说明root的左右子树当中分别存在节点p/q，返回root

C++

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==NULL) return NULL; if(root==p || root==q) return root; TreeNode* left=lowestCommonAncestor(root->left, p,q); TreeNode* right=lowestCommonAncestor(root->right, p,q); if(left==NULL&&right!=NULL) return right; if(left!=NULL&&right==NULL) return left; if(left==NULL&&right==NULL) return NULL; return root; } };

python

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if not root or root==p or root==q: return root left = self.lowestCommonAncestor(root.left,p,q) right = self.lowestCommonAncestor(root.right, p,q) if not left: return right if not right: return left return root

参考引用资料

具体的图解，见Krahets大佬的文章。
Krahets 160. 相交链表（双指针，清晰图解）

236. 二叉树的最近公共祖先（DFS ，清晰图解）