C语言每日一题（31）相交链表

对编程一片赤诚的小吴

发布于 2024-01-23 15:08:50

780

发布于 2024-01-23 15:08:50

文章被收录于专栏：热爱编程的证据热爱编程的证据

力扣160.相交链表

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

思路分析

首先明确题目所要求的：

1.两链表是否相交？

2.如果相交的话，交点在哪？

首先解决第一个问题，判断是否相交。首先两个链表的头结点可能一样也可能不一样，但如果相交的话，它们的尾结点一定是同一个，那么我们可以分别遍历这两个链表到尾，如果一样的话就代表它们一定相交，否则直接返回false。

到第二个问题，找交点，如果俩链表同时从头遍历，再找它们相同的结点的话，那么当俩链表长度不同，指针就会错位，这是不靠谱的做法，正确的做法是，将它们遍历的起点进行统一后再进行遍历，直到碰到相同的结点，就是它们的交点。

如何统一起点呢？

首先找出较长链表，将俩链表长度的差当作步数，让长链表的指针先走完这些步数，这样两个链表的指针就统一了，之后两个指针再一起遍历，直到碰到相同结点停止，返回任意一个指针即是对应的交点。

完整代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA,*curB=headB;
    int lenA=1,lenB=1;//从1开始。
    while(curA)
    {
        lenA++;
        curA=curA->next;
    }
    while(curB)
    {
        lenB++;
        curB=curB->next;
    }
    if(curA!=curB)/判断是否相交
    {
        return NULL;
    }
    int n=abs(lenA-lenB);
    struct ListNode* longlist=headA,*shortlist=headB;//可以先假设其中一个为长链表。
    if(lenB>lenA)//如果不是在交换即可。
    {
        longlist=headB;
        shortlist=headA;
    }
    while(n--)//长指针先走
    {
        longlist=longlist->next;
    }
    while(shortlist!=longlist)//两个一起走，直到相同停下
    {
        shortlist=shortlist->next;
        longlist=longlist->next;
    }
    return longlist;//返回其中任意一个即可。
}