BM10. [两个链表的第一个公共结点]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM10. 两个链表的第一个公共结点

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=295&sfm=github&channel=nowcoder

题目分析

题目也非常的好玩，思路其实就是各自遍历，到达终点之后从对方的起始节点开始遍历，如果有公共节点，那么交换两次次之后必然能够遇到。

看图其实更容易理解

做法分析

判断如果任意一方为空，那么公共节点就是null

if(pHead1 == null || pHead2 == null)
    return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
int change = 0;

设置p1遍历节点，设置p2遍历节点，如果p1==p2证明当前节点就是公共节点，循环过程如果为空，就将对方的头节点赋值给当前节点，设置交换次数标识计数器change，如果大于两次终止循环。跳出循环没有找到所以返回值为null

int change = 0;
while(true){
    if(p1 == p2)
    return p1;
    p1 = p1.next;
    p2 = p2.next;
    if(p1 == null){
    p1 = pHead2;
    change++;
    }
    if(p2 == null){
    p2 = pHead1;
    change++;
    }
    if(change > 2)
    break;
}
return null;

完整题解

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if(pHead1 == null || pHead2 == null)
        return null;
    ListNode p1 = pHead1;
    ListNode p2 = pHead2;
    int change = 0;
    while(true){
        if(p1 == p2)
            return p1;
        p1 = p1.next;
        p2 = p2.next;
        if(p1 == null){
            p1 = pHead2;
            change++;
        }
        if(p2 == null){
            p2 = pHead1;
            change++;
        }
        if(change > 2)
            break;
    }
    return null;
}

复杂度分析
时间复杂度：，交换两次节点之后肯定相遇，不过查过，所以时间复杂度是

空间复杂度：，没有使用额外的空间