题目
输入两个链表，找出它们的第一个公共结点。
分析
最直观的想法是，从链表A的第一个节点开始遍历，去和链表B的每一个节点匹配，对个匹配成功的就是答案。
这个方法的时间复杂度是O(mn)。
我们可以考虑以空间换时间。
题目中给了这个链表是单链表，形式如下：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
这是单链表，每一个节点只有一个指向下一个节点的指针，或者没有指向下一个节点的指针。
因此从第一个相同的节点之后，两个链表的后面应该是一样的。
那么如果我们能从链表的最后开始往前进行比较，每一个都应该是一样的，直到相同节点的。
很自然想到要用栈，先将两个链表分别压栈，然后每一次比较栈顶元素，并进行出栈。
代码
/*
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) {
if (pHead1 == null || pHead2 == null) {
return null;
}
// 首先各自压栈
Stack<ListNode> stack1 = new Stack<>();
Stack<ListNode> stack2 = new Stack<>();
while (pHead1!= null) {
stack1.push(pHead1);
pHead1 = pHead1.next;
}
while(pHead2 != null){
stack2.push(pHead2);
pHead2 = pHead2.next;
}
// 并行出栈，一一对比
ListNode result = null;
while(stack1.isEmpty() == false && stack2.isEmpty() == false && stack1.peek() == stack2.peek()){
stack1.pop();
result = stack2.pop();
}
return result;
}
}
这里需要注意的是，每一次比较的时候要使用stack.peek()方法，这个方法只会取栈顶元素的值，但是不会像stack.pop()将元素出栈。方便我们后面利用栈顶元素进行结果 的返回。
