牛客网在线编程专题《剑指offer

在线编程专题《剑指offer"/>

牛客网在线编程专题《剑指offer

题目链接：

=13&tqId=11189&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

解题思路：

首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个结点。在第二次遍历的时候，在较长的链表上先走若干步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个公共结点。

如上图所示的两个链表中，我们可以先遍历一次得到它们的长度分别为5和4，也就是较长的链表与较短的链表相比多一个结点。第二次先在长的链表上走1步，到达结点2。接下来分别从结点2和结点4出发同时遍历两个结点，直到找到它们第一个相同的结点6，这就是我们想要的结果。

时间复杂度为O（m+n）。

已经AC的代码：

public class firstCommonNode {class ListNode{int val;ListNode next = null;public ListNode(int val) {// TODO Auto-generated constructor stubthis.val = val;}}public static void main(String[] args) {// TODO Auto-generated method stubfirstCommonNode ownClass = new firstCommonNode();ListNode l1_one = ownClass.new ListNode(1);ListNode l1_two = ownClass.new ListNode(2);l1_one.next = l1_two;ListNode l1_thr = ownClass.new ListNode(3);l1_two.next = l1_thr;ListNode l1_for = ownClass.new ListNode(6);l1_thr.next = l1_for;ListNode l1_fiv = ownClass.new ListNode(7);l1_for.next = l1_fiv;ListNode l2_one = ownClass.new ListNode(4);ListNode l2_two = ownClass.new ListNode(5);l2_one.next = l2_two;l2_two.next = l1_for;ListNode node = FindFirstCommonNode(l1_one, l2_two);System.out.println(node.val);}public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {//得到两个链表的长度int nLength1 = getListLength(pHead1);int nLength2 = getListLength(pHead2);//得到两个链表长度之间的差值int nLengthDif = nLength1 - nLength2;ListNode pListHeadLong = null;ListNode pListHeadShort = null;if(nLengthDif >=0) {pListHeadLong = pHead1;pListHeadShort = pHead2;}else {pListHeadLong = pHead2;pListHeadShort = pHead1;nLengthDif = nLength2 - nLength1;}// 先在长链表上走几步，再同时在两个链表上遍历for(int i=0; i<nLengthDif; i++) {pListHeadLong = pListHeadLong.next;}// 同时在两个链表上遍历while((pListHeadLong != null) && (pListHeadShort != null) && (pListHeadLong != pListHeadShort)) {pListHeadLong = pListHeadLong.next;pListHeadShort = pListHeadShort.next;}//得到第一个公共结点ListNode pFirstCommonNode = pListHeadLong;return pFirstCommonNode;}public static int getListLength(ListNode pHead) {int nLength = 0;ListNode pNode = pHead;while(pNode != null) {nLength++;pNode = pNode.next;}return nLength;}}