题目描述

输入两个链表，找出它们的第一个公共结点。
当不存在公共节点时，返回空节点。

算法一

差值法

核心就是将长度不同的两个链表，通过让一个链表的指针先走，从而达到让两个链表的剩余长度相同，再同时移动指针，从而找到第一个共同的节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL||headB==NULL||headA->next==NULL||headB->next==NULL)return NULL;
        //统计链表的长度
        int l1=0,l2=0;
        auto a=headA;
        auto b=headB;
        while(a){
            l1++;
            a=a->next;
        }
        while(b){
            l2++;
            b=b->next;
        }
        int sub=0;
        a=headA;
        b=headB;
        while(l1>=l2&&sub<l1-l2){
            sub++;
            a=a->next;
        }
        while(l1<l2&&sub<l2-l1){
            sub++;
            b=b->next;
        }
        while(a&&b){
            if(a==b)return a;
            a=a->next;
            b=b->next;
        }
        if(!a)return NULL;
    }
};

算法二

双指针

双指针如果是空，即没有公共节点，就是两个指针同时为空。
当一个指针为空时，就要将这个指针指向另一个链表的头

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto a=headA;
        auto b=headB;
        while(a!=b){
            if(!a)a=headB;
            else a=a->next;     //要么移到下一个链表的头，要么移到下一位，else必须要
            if(!b)b=headA;
            else b=b->next;
        }    
        return a;
    }
};