题解 | #两个链表的第一个公共结点#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
#include <stdlib.h>
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode *p,*q;
    //p=(struct ListNode*)malloc(sizeof(struct ListNode));
  //先求出两个链表的长度
    int i=0,j=0;
    int bigLen=0,smallLen=0;
    p=pHead1;
    while(p!=NULL){
        i++;
        p=p->next;
    }
    p=pHead2;
    while (p!=NULL) {
        j++;
        p=p->next;
    }
  //p指向短链表头，q指向长链表头
    if(i<j){
        p=pHead1;
        q=pHead2;
        bigLen=j;
        smallLen=i;       
    }else{
        p=pHead2;
        q=pHead1;
        bigLen=i;
        smallLen=j;
    }
  //移动长链表，让两个指针指向的位置距离各自链表的尾部长度一致
    for(;bigLen>smallLen;bigLen--){
        q=q->next;
    }   
    while (bigLen>=0) {
	  //判断两个指针指向的位置是否相同
        if(p==q){
            return p;
        }
        p=p->next;
        q=q->next;       
    }
    return NULL;
}