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

/**
 * 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 ) {
    struct ListNode* p1 = pHead1;   //p1辅助遍历第一个链表
    struct ListNode* p2 = pHead2;   //p2辅助遍历第二个链表
    struct ListNode* s = NULL;  //s辅助构建公共结点的链表

     //新建一个带头结点的链表，带头结点方便尾插法插入，用来存储公共结点
    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));   
    newnode ->next = NULL;
    struct ListNode* pnew = newnode;    //pnew用于遍历记录公共结点链表的尾部，便于从插入

    int flag = 0;   //flag标志位，默认为0，即遍历到两链表的结点值不相等
    int len1 = 0, len2 = 0,ret = 0; //len1，len2分别求长度，ret为更长的那个链表的起始遍历位置

    while(p1){
        len1++;
        p1 = p1->next;
    }
    while (p2) {
        len2++;
        p2 = p2->next;
    }
    p1 = pHead1;    //再求完长度后重置p1和p2
    p2 = pHead2;

    //看哪个链表更长，长的那个从多出的结点之后开始遍历，使两链表遍历长度相等
    if(len1>len2){ 
        ret = (len1 - len2)+1;
        for(int i=1; i<ret; i++){
            p1=p1->next;
        }
    }else if(len1<len2){
        ret = (len2-len1)+1;
        for (int i=1; i<ret; i++) {
            p2 = p2->next;
        }
    }else{
        ret = 1;
    }

    //开始遍历两链表
    while (p1 && p2) {
        if(p1->val==p2->val){   //如果遍历的位置相等，flag值置为1，表示相等
            flag = 1;
            s = p1; //s保存两链表相等的结点，任意取两链表被遍历结点之一都行
            p1 = p1->next;  //p1,p2继续向后遍历
            p2 = p2->next;
            pnew->next = s; //将相等结点插入公共结点链表
            s->next = NULL;
            pnew = pnew->next;  //pnew继续向后记录公共链表的最后一个结点
        }else{
            flag = 0;   //一旦遇到不相等的，flag置为1，表示不是公共结点
            newnode->next = NULL;   //只要遍历中有一处不相等，则重头建立公共结点链表
            p1 = p1->next;
            p2 = p2->next;
        }
    }

    if (0 == flag) {    //对两链表遍历完成后flag任然是0,表示连一个公共结点都没有
        return NULL;    //返回NULL
    }else{
        return newnode->next;   //遍历完成后flag值为1，表示至少有一个公共结点，返回用来记录公共结点链表的头结点
    }
}