剑指offer 36.两个链表的第一个公共结点

剑指offer 36.两个链表的第一个公共结点

题目

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

思路

如果可以的话，从后往前比较最合适。但是不行，我们需要考虑两个链表的长度不同，长度为len1和len2，长的先走完差值，然后两个一起往后面走，就可以找到相同的结点。

代码

  public class ListNode {

    int val;
    ListNode next = null;

    ListNode(int val) {
      this.val = val;
    }
  }

  public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if (pHead1 == null || pHead2 == null) {
      return null;
    }
    ListNode p1 = pHead1;
    ListNode p2 = pHead2;
    int len1 = 0;
    int len2 = 0;
    while (p1.next != null) {
      len1++;
      p1 = p1.next;
    }
    while (p2.next != null) {
      len2++;
      p2 = p2.next;
    }
    p1 = pHead1;
    p2 = pHead2;
    if (len1 > len2) {
      for (int i = len1 - len2; i >= 0; i--) {
        p1 = p1.next;
      }
    } else {
      for (int i = len2 - len1; i >= 0; i--) {
        p2 = p2.next;
      }
    }
    while (p1 != p2) {
      p1 = p1.next;
      p2 = p2.next;
    }
    return p1;
  }