牛客高频算法题系列-BM10-两个链表的第一个公共节点问题描述输入两个对于非循环单链表，求它们的第一个公共节点，如果没有公共节点则返回空。（注意因为传入的数据是链表，测试数据错误的提示用其他方式显示，确保传入的数据正确）参见原标题：BM10两个链表的第一个公共节点解决方案1：双循环使用双循环遍历2个链表简单粗暴，但效率略低。方案二：双指针法用两个指针l1和l2分别从链表1和链表2的头节点开始遍历。遍历到最后，分别从链表2和链表1开始遍历。如果两个链表有公共交点，则l1和l2一定在交点处相交，否则分别遍历两个链表后l1和l2都为null，没有公共节点。代码publicclassBm010{/***方法一：双循环**@parampHead1链表1*@parampHead2链表2*@return*/publicstaticListNodefindFirstCommonNode(ListNodepHead1,ListNodepHead2){if(pHead1==null||pHead2==null){返回null;}ListNodenode1=pHead1;//外层循环遍历链表1的节点while(node1!=null){ListNodenode2=pHead2;//内层循环遍历链表2的节点Nodewhile(node2!=null){if(node2==node1){returnnode1;}node2=node2.next;}node1=node1.next;}返回空值；}/***双指针法**@parampHead1*@parampHead2*@return*/publicstaticListNodefindFirstCommonNode2(ListNodepHead1,ListNodepHead2){//l1和l2从链表1的头节点遍历并链接分别从链表2遍历到末尾后，再分别从链表2和链表遍历ListNodel1=pHead1,l2=pHead2;而（l1！=l2）{l1=(l1==null)?pHead2:l1.next;l2=(l2==null)?pHead1:l2.next;}//如果两个链表有公共交集，那么l1和l2一定在交集处相遇，此时l1为公共节点//否则分别遍历两个链表后l1和l2都为null，有没有公共节点，返回nullreturnl1；}publicstaticvoidmain(String[]args){ListNodepHead1=ListNode.testCase2();System.out.println("列表一是");ListNode.print(pHead1);ListNodepHead2=ListNode.testCase1();pHead2.next.next.next=pHead1.next.next;System.out.println("第二个链表是");ListNode.print(pHead2);ListNode.print(findFirstCommonNode(pHead1,pHead2));ListNode.print(findFirstCommonNode2(pHead1,pHead2));}}$1.01^{365}≈37.7834343329$$0.99^{365}≈0.02551796445$相信坚持的力量！
