当前位置：首页 > article >正文

【数据结构】_链表经典算法OJ：相交链表

article 2025/2/3 14:20:07

1. 题目链接及描述

2. 解题思路

2.1 思路1：一个链表把另外一个链表的结点逐个轮一遍

2.2 思路2：截断长链表，从距离交点结点前等距处开始同时遍历（本题解法）

3. 程序

关于解题程序的细节：

3.1 假设法的应用：

3.2 关于链表长度的计算

1. 题目链接及描述

题目链接：160. 相交链表 - 力扣（LeetCode）

题目描述：

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

题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。

2. 解题思路

拆解题目要求：1、判断是否相交；2、若相交则找出第一个交点；

判断两个单链表是否相交：判断两个链表的尾指针是否相等，相等则相交，不等则不相交；

注：1、本题不可逆置：否则在交点结点处存在两个next指针域，；

一个结点不允许存在两个next指针域；

2、判断尾指针相等与否需要用地址判断，不能用val值判断；

2.1 思路1：一个链表把另外一个链表的结点逐个轮一遍

为两个链表分别创建结构体指针curNodeA和curNodeB，用第二个链表的每一个结点依次把第一个链表的所有结点都比一遍，直至交点结点处会相等；

时间复杂度O(N^2)；

注：两个指针不可同时走，若相交结点前两个链表长度不同，则会导致即使相交也被判定为不相交的情况；

2.2 思路2：截断长链表，从距离交点结点前等距处开始同时遍历（本题解法）

分别计算两个链表的长度，若长度相等则直接从第一个结点处开始同时遍历并依次对比；

长度不等则截断长链表，从与短链表第一个结点到交点结点前处的结点开始同时遍历并依次对比；

时间复杂度O(N)；

3. 程序

/**
 * 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* curNodeA=headA,*curNodeB=headB;
    // 分别计算两个链表长度
    int lenA=1,lenB=1;
    while(curNodeA->next){
        curNodeA=curNodeA->next;
        lenA++;
    }
    while(curNodeB->next){
        curNodeB=curNodeB->next;
        lenB++;
    }
    // 两个链表直至遍历到尾结点，指针都不等：两个链表不相等；
    if(curNodeA != curNodeB){
        return NULL;
    }
    // 令长链表的遍历指针先走差值步，再同时遍历，第一个相等就是交点
    int gap=abs(lenA-lenB);
    // 假设法：假设A长B短
    ListNode* longList=headA,*shortList=headB;
    // 若假设错误则修正
    if(lenB>lenA){
        longList=headB;
        shortList=headA;
    }
    while(gap--){
        longList=longList->next;
    }
    while(longList != shortList){
        shortList=shortList->next;
        longList=longList->next;
    }
    return shortList;
}