C语言/数据结构——（相交链表）

一.前言

今天在力扣上刷到了一道题，想着和大家一起分享一下这道题——相交链表https://leetcode.cn/problems/intersection-of-two-linked-lists废话不多说，让我们开始今天的分享吧。

二.正文

1.1题目描述

是不是感觉好长，我也这么觉得。哈哈，不过没办法，大家们凑合看一下吧，毕竟人家的题就那么长。

1.2题目分析

我想到有两种方法，一种是暴力求解，时间复杂度是O（N^2），还有一种是一种稍微巧妙一点的技巧，时间复杂度是(N)。

两种方法共同部分：

我们可以创建两个指针分别是指向headA和headB的，pcur1和pcur2。并让pcur1=headA

pcur2=pcurB。

我们首先需要判断该链表是不是相交链表，如果是，则返回相交链表的第一个相交节点。否则，返回NULL。那么如何判断该链表是不是相交链表呢？其实我们可以让pcur1和pcur2分别遍历两个链表的最后一个节点即可，如果pcur1=pcur2则说明两个链表至少有一个相交节点，毫无疑问这肯定是相交节点。反之，pcur1！=pcur2，则说明，不是相交链表。（值得注意的是，完成上面部分后，记得让pcur1=headA，pcur2=headB，因为pcur1和pcur2后续我们还需要重新遍历两个链表）

（i）暴力算法：

我们可以让headA中的每一个节点都与headB中的节点遍历一次，然后让headA的下一个节点，重复这个动作，直到headA的最后一个节点遍历结束。

这是该方法的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
ListNode* pcur1,*pcur2;
pcur1=headA;
pcur2=headB;
while(pcur1->next!=NULL)
{
    pcur1=pcur1->next;
}
while(pcur2->next!=NULL)
{
    pcur2=pcur2->next;
}
if(pcur2!=pcur1)
return NULL;
pcur1=headA;
pcur2=headB;
while(pcur1->next!=NULL)
{
while(pcur2->next!=NULL)
{
if(pcur1==pcur2)
return pcur1;
pcur2=pcur2->next;
}
pcur2=headB;
pcur1=pcur1->next;
}
return pcur1;
}