【数据结构与算法经典例题】相交链表求交点

倔强的石头_

发布于 2024-12-06 18:58:35

4670

文章被收录于专栏：C/C++指南C/C++指南

一、问题描述

160. 相交链表 - 力扣（LeetCode）

如下图所示

二、解题思路

方法一:双循环对比法

时间复杂度O（n^2）空间复杂度O（1）
链表A中的节点依次与链表B中的每个节点比较
若出现节点相同，则相交且为第一个交点
若链表A走到空依然没有相同的节点，则不相交

注意：暴力解法效率较低，不建议采用

方法二: 双指针法

时间复杂度O（n) 空间复杂度O（1）
首先遍历链表求出两个链表的长度，求得长度的差值
定义两个快慢指针，哪个链表长，快指针就指向哪个链表
两个指针分别从两个链表的第一个节点开始遍历，快指针先走出一个长度差值，之后两个指针每移动一步，比较指向的节点是否相同
若出现节点相同，则相交且为第一个交点
若两个指针走到空依然没有相同的节点，则不相交

三、C语言代码实现

方法一实现代码

 struct ListNode 
{
    int val;
    struct ListNode *next;
};

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    ListNode*pcurA=headA;
    ListNode*pcurB=headB;
    while(pcurA)
    {
        pcurB=headB;
        while(pcurB)
        {
            if(pcurA==pcurB)
                return pcurA;
            pcurB=pcurB->next;
        }
        pcurA=pcurA->next;
    }
    return NULL;
}

方法二实现代码

 struct ListNode 
{
    int val;
    struct ListNode *next;
};

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
   ListNode*pcurA=headA;
   ListNode*pcurB=headB;
   int countA=0;
   int countB=0;
   while(pcurA)//求出链表长度
   {
        pcurA=pcurA->next;
        countA++;
   }
   while(pcurB)
   {
        pcurB=pcurB->next;
        countB++;
   }
   int tmp=abs(countA-countB);//长度差值
   ListNode*slow,*fast;
   if(countA<countB)
    {
        slow=headA;
        fast=headB;
    }
    else
    {
        slow=headB;
        fast=headA;
    }
    while(tmp--)//长链表先走差值的步数
    {
        fast=fast->next;
    }
    while(fast&&slow)//同步比较
    {
        if(fast==slow)
            return fast;
        fast=fast->next;
        slow=slow->next;
    }
    return NULL;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-05-30，如有侵权请联系 cloudcommunity@tencent.com 删除

struct