一、题目描述
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
要求：时间复杂度不超过O(n),空间复杂度不超过O(1)。
二、解题思路
对于该题我首先想到的是对两个链表同时进行遍历，若两个结点相同，则直接返回相同结点，但是提交之后无法通过，最后发现我的这种解法只适合等长链表求相同结点，这种解法并不可行。
正确解法：
由于时间复杂度不超过O(n)，那么最多只能遍历一次，我们可以设置两个结点分别指向链表的首元结点，两个链表都进行遍历，就是如果当前的链表遍历完之后，就让其遍历另一条链表，因为遍历的速度一样，且遍历的总长度一样，如果有相同结点则一定会在遍历结束前找到，否则没有相同结点。
三、代码实现
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode cur1=pHead1; ListNode cur2=pHead2; while(cur1!=cur2){//这里未用equals原因是题目要求的结点相同，不仅仅是内容上相同，更重要的是地址相同，也就是同一个结点。 if(cur1==null){ cur1=pHead2; }else{ cur1=cur1.next; } if(cur2==null){ cur2=pHead1; }else{ cur2=cur2.next; } } return cur1; } }
