有三种情况：

1、 两个链表都没有环
2、 一个链表有环，一个链表无环
3、 两个链表都有环

参考文章：求两个单链表的交点 作者：yingsun

1、如果两个链表都没有环的话，会像下图这样，呈“Y”型

实现代码如下

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) :  val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *head1, ListNode *head2) {
        if(!head1 || !head2)   //如果其中一个链表为空，返回NULL
            return NULL; 
    
        unsigned int len1 = getLength(head1);    //获取2个链表的长度
        unsigned int len2 = getLength(head2);

        int diff = len1 - len2;                  //获得两个长度差
        ListNode *longList = head1;
        ListNode *shortList = head2;
        
        if(len1 < len2) {
            longList = head2;
            shortList = head1;
            diff = len2 - len1;
        }

        while(diff--) {
            longList = longList->next;   //长的链表先走diff步
        }
        while(longList && shortList && (longList != shortList) ) {
            shortList = shortList->next;
            longList = longList->next;
        }
        ListNode *firstCommonNode = shortList;
        
        return firstCommonNode; 
    }

    unsigned int getLength(ListNode *head) {    //获得链表长度的方法
        unsigned int length = 0;
        ListNode *node = head;
        while(!node) {
            length++;
            node = node->next;
        }
        return length;
    }

};

2、如果两个链表其中一个有环，其中一个无环

这种情况，两者根本不会有交点，不用考虑

原因是：一旦它们有一个交点，若其中一个有环，那么另一个也必然有环。由单链表的一个结点仅有一个后继结点的性质决定。

3、如果两个链表都有环

如果有环，第一种情况的方法获取链表的长度的方法就不可靠了。但是我们还是有办法算出带有环的链表的长度——在判断链表是否有环的题目中得到启发。但第一种情况的代码依然可用

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) :  val(x), next(NULL) {}
};

class Solution {
public:
      ListNode *findFirstCommonNodeFinalVersion(ListNode *head1, ListNode *head2) {
          if(!head1 || !head2)
              return NULL;

          unsigned int len1, len2;

          len1 = hasCycle(head1) ? cycleListLength(head1) : getLength(head1);
          len2 = hasCycle(head2) ? cycleListLength(head2) : getLength(head2);
          
          int diff = len1 - len2;
          int shorter = len2;
          ListNode *longList = head1;
          ListNode *shortList = head2;
          
          if(len1 < len2) {
              diff = len2 - len1;
              shorter = len1;
              longList = head2;
              shortList = head1;
          }

          while(diff--)
              longList = longList->next;
          while(shorter-- && (longList != shortList)) {
              longList = longList->next;
              shortList = shortList->next;
          }
          ListNode *firstCommonNode = shortList;

          return firstCommonNode;          
      }

      bool hasCycle(ListNode *head) {  //判断链表是否有环的方法
          ListNode *slow = head, *fast = head;
          while(fast != NULL && fast->next != NULL) {
              slow = slow->next;
              fast = fast->next->next;
              if(slow == fast)
                  return true;
          }
          return false;
      }

      unsigned int getLength(ListNode *head) { //获取无环链表长度的方法
          unsigned int length = 0;
          ListNode *node = head;
          while(node != NULL) {
              length++;
              node = node->next;
          }
          return length;
      }

      unsigned int cycleListLength(ListNode *head) { //获取有环链表长度的方法
          unsigned int length = 0;
          ListNode *slow = head, *fast = head;
          while(slow!=fast) {
                slow = slow->next;
                fast = fast->next->next;
          }
          slow = head;
          while(slow!=fast) {
              length++;
              slow = slow->next;
              fast = fast->next;
          }
          while(fast!=slow) {
              length++;
              fast = fast->next;  
          }
          length++;
          return length;
      }
};

为了使代码简洁，可读性好，遍历2个链表的次数会比较多，牺牲了一些性能