LeetCode 160. 相交链表

目录

1.原题链接：

2.链表相交的概念：

3.对齐链表： 

代码实现：

4.双指针： 

代码实现：

 5.提交结果：

6.读书分享：

---

1.原题链接：

160. 相交链表

2.链表相交的概念：

首先，我们要对链表的相交有个清晰的认知，要知道在单链表中，一个结点只能指向一个next结点，不能有多个，但是可以有多个结点指向它。

所以， 不会存在这样的结构：

而只会是这种类型的：

 

3.对齐链表： 

对于本题，我们可以先把两个链表都遍历一遍，求出两个链表各自的结点数量，若两个链表的结点数量不同，我们就先让结点多的链表先走几个结点（多出结点的数量个），要知道，如果链表相交，多出的结点肯定在相交的结点之前（因为在相交结点之后，大家都是共用同样的结点，不会再分叉了）。最后，我们再让两个链表的指针同时向后遍历，遇到同一个结点了，说明链表相交；如果后面指向NULL了，就不相交。

代码实现：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* lA=headA;
    ListNode* lB=headB;
    int countA=0,countB=0;
    //1.计算两个链表的长度
    while(lA!=NULL)
    {
        countA++;
        lA=lA->next;
    }
    while(lB!=NULL)
    {
        countB++;
        lB=lB->next;
    }
    //遍历完后，重新回到头结点
    lA=headA;
    lB=headB;
    //2.让结点多的多走几步
    while(countA>countB)
    {
        lA=lA->next;
        countA--;
    }
    while(countB>countA)
    {
        lB=lB->next;
        countB--;
    }
    //3.两个指针同时遍历，找到相交结点，返回
    while(lA!=lB)
    {
        if(lA==NULL||lB==NULL)
            return NULL;
        lA=lA->next;
        lB=lB->next;
    }
    return lA;
}

4.双指针： 

如果链表相交：

我们设A链表的不相交部分为x，B链表的不相交部分为y，两个链表相交部分为z，则A链表的长度为x+z，B链表的长度为y+z 。

如果x=y，则两个指针会同时遍历到相交结点，直接返回就行。

如果x≠y，我们可以让lA指针遍历完A链表后，再去遍历B链表；让lB指针遍历完B链表后，再去遍历A链表。这样，lA指针遍历x+z+y次，lB遍历y+z+x次后，就相当于两个链表的长度相等了，这样，两个指针就会同时到达两个链表相交的节点。

如果链表不相交：

如果A链表与B链表长度相等，两个指针会同时指向NULL。

如果A链表与B链表长度不相等，由于两个链表没有公共节点，并且两个指针也不会同时到达各自链表的尾节点，因此两个指针都会在遍历完两个链表后，再返回NULL，此时lA遍历的长度为x+z+y+z ,lB遍历的长度为y+z+x+z。

代码实现：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL||headB==NULL)
        return NULL;
    ListNode* lA=headA;
    ListNode* lB=headB;
    while(lA!=lB)
    {
        if(lA==NULL)//当A链表遍历完
            lA=headB;
        else
            lA=lA->next;
        if(lB==NULL)//当B链表遍历完
            lB=headA;
        else
            lB=lB->next;
    }
    return lA;
}

 5.提交结果：

6.读书分享：

《道德经·第四十五章》：

大成若缺，其用不弊。

大盈若冲，其用不穷。

大直若屈，大巧若拙，大辩若讷。

静胜躁，寒胜热。清静为天下正。

解释：

最完满的东西好像有欠缺一样，但是它的作用是不会衰竭的。

最充盈的东西好像是空虚一样，但是它的作用是不会穷尽的。

最正直的东西好像是弯曲的一样，最灵巧的东西好像是笨拙的一样，最卓越的辩才好像是木讷的一样。

清静克服扰动，寒冷克服暑热。清静无为可以使天下太平。