《手撕链表题系列-8》相交链表_相交链表 手撕

前言

本系列主要讲解链表的经典题

注：划重点！！必考~

链表分割

力扣链接：160. 相交链表 - 力扣（LeetCode） (leetcode-cn.com)

• 题目描述：

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

• 示例：

• 提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 0 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

• 解题思路：

1. 对两个链表进行分别遍历算出长度差
2. 同时如果两链表末尾结点地址不同，则表示没有两链表没有相交
3. 对长链表指针先走长度差个结点，再两个指针同时遍历
4. 当两个结点指针相遇时即为相交节点

• 参考代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //创建寻址指针
    struct ListNode*cur1=headA,*cur2=headB;
    //计算各链表的长度
    int len1=1,len2=1,gas;
    while(cur1->next)
    {
        len1++;
        cur1=cur1->next;
    }
    while(cur2->next)
    {
        len2++;
        cur2=cur2->next;
    }
    //各链表尾节点不相等则两链表不相交
    if(cur1!=cur2)
    return false;
    //接下来则是必定有相交节点的情况
    //判断长短并记录
    struct ListNode*geater,*less;
    if(len1>=len2)
    {
        geater=headA;
        less=headB;
        gas=len1-len2;
    }
    else
    {
        geater=headB;
        less=headA;
        gas=len2-len1;
    }
    //长链表先走差距长度
    while(gas--)
    {
        geater=geater->next;
    }
    //一同走，相等时则找到相交节点
    while(geater!=less)
    {
        geater=geater->next;
        less=less->next;
    }
    return geater;
}

• 结果：

 每日k题无烦恼，点赞学习不得了~