判断链表相交

墨蓝 2023-09-26 17:23 30阅读 0赞

### 链表相交 ###

leetcode题目第141道

#### 问题描述： ####

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

例如：  
![在这里插入图片描述][9b0f10db3c39493e877b7e504b6e05c3.png]  
(图片来自LeetCode，侵删)

#### 解题思路 ####

##### 步骤1. #####

首先需要判断两个链表是否相交，毕竟链表相交才能进行下一步操作。  
但怎么判断两个链表怎么相交呢？很简单，**判断两个链表的尾结点是否为同一个结点**  
只要两链表的最后一个结点是同一个结点，那么链表必定相交，此结论可通过画出链表结点图可得出。

##### 步骤2. #####

在得出两链表相交的情况下，来返回两个链表相交的起始节点。  
**首先分别获取两个链表的长度lenListA与lenListB，然同用快慢指针法，先让较长的链表走N步，N=(lenListA-lenListB)的绝对值。然后两个链表再同时走，直到两个链表的结点是一样的，此时这个结点就是两个链表相交的起始节点**  
例如：  
![在这里插入图片描述][337ec38511ba43488c6009476dd7f202.png]  
此时较长的链表为B，所以让链表B先走N步。

#### 代码实现 ####

##### 方法一：快慢指针法 #####

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
    {
        
        struct ListNode *data=NULL;
        struct ListNode *curHeadA=headA;
        struct ListNode *curHeadB=headB;
        int lenA=1,lenB=1;
        /*获取两个链表长度*/
        /*并将两链表分别迭代到各自尾节点*/
        while(curHeadA->next != NULL)
        {
        
            ++lenA;
            curHeadA=curHeadA->next;
        }
        while(curHeadB->next != NULL)
        {
        
            ++lenB;
            curHeadB=curHeadB->next;
        }
        //如果尾结点不相等，那么就是不相交
        if(curHeadA != curHeadB)
        {
        
            return NULL;
        }
    	//获得两个链表长度的差值
        int gap=abs(lenA-lenB);	//注意abs是获取绝对值函数
        //默认headA为长链表
        struct ListNode *LongList=headA;
        struct ListNode *shortList=headB;	
    	//如果是headB为更长的链表，则将LongListA与shortList调换指向对象
        if(lenA < lenB)
        {
        
            LongList=headB;
            shortList=headA;
        }
        //longlist 指向更长的那条链表
        //然后再先走 长度的差值步
        while(gap--)
        {
        
            LongList=LongList->next;
        }
        //两个指针一起走到相交结点就退出
        while(LongList != shortList)
        {
        
            LongList=LongList->next;
            shortList=shortList->next;
        }
        //返回相交结点
        return LongList;
    }

**运行结果：**  
![在这里插入图片描述][0f8cfcd319ca45e0a865deec577441a7.png]

##### 方法二：暴力迭代法 #####

**注意：不推介使用这个方法解这个题目，因为时间复杂度太大了，可能在面试中用这个解法容易被面试官叉出去(doge)**

###### 思路： ######

将链表A的每一个节点和链表B的每一个节点比较一遍，如果有节点相等的则返回相等节点，
    如果比较循环结束后那么默认没有相交节点。

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
    {
        
    	struct ListNode *curHeadA=headA;
        struct ListNode *curHeadB=headB;
    	/*暴力循环破解*/
         while(curHeadA !=NULL)
         {
        
             curHeadB=headB;
             while(curHeadB != NULL)
             {
        
             	//当两链表节点相等时，代表两链表相交，并返回相交的起始节点
                 if(curHeadA == curHeadB)
                 {
        
                     return curHeadA;
                 }
                curHeadB=curHeadB->next; 
             }
             curHeadA=curHeadA->next;
         }
         return NULL;
     }

**运行结果：**  
![在这里插入图片描述][24703d5fbec3477d9c2181eebba36ff1.png]

#### 总结 ####

个人觉得这个题目主要考察的是对快慢指针的认知，**如有错误，欢迎指出，共同进步。**

[9b0f10db3c39493e877b7e504b6e05c3.png]: https://img-blog.csdnimg.cn/9b0f10db3c39493e877b7e504b6e05c3.png
[337ec38511ba43488c6009476dd7f202.png]: https://img-blog.csdnimg.cn/337ec38511ba43488c6009476dd7f202.png
[0f8cfcd319ca45e0a865deec577441a7.png]: https://img-blog.csdnimg.cn/0f8cfcd319ca45e0a865deec577441a7.png
[24703d5fbec3477d9c2181eebba36ff1.png]: https://img-blog.csdnimg.cn/24703d5fbec3477d9c2181eebba36ff1.png