数据结构练级之路【判断两条链表是否有交点】题目讲解

简介: 数据结构练级之路【判断两条链表是否有交点】题目讲解

一、题目:

1.(相交链表)(只能聚合,不能发散,Y字形,不是X字形)

给你两个单链表的头结点headA,headB,请你找出并返回相交单链表的起始结点,如果两个链表没有交点就返回NULL;


思路一:(暴力求解法)遍历A链表,依次取A链表中的每一个结点,依次跟B链表中的的所有结点比较,如果有地址相同的结点,就是相交,第一个相同的交点(前提是要让我的链表的长度保持一致)

思路二:优化从O(N^2)到 O(N)

1.尾结点相同就是相交,否则就是不想交(因为如果这个链表是一个有交点的链表,那么它的尾结点就一定是相交的,因为链表只能是Y 字形的结构,不是X字形的结构)

所以此时直接找尾,然后判一下就行了

2.求交点:此时就是想让这个代码是时间复杂度为O(2*N),就是双指针一起向后走(然后同一个位置的结点进行比较,如果相同就表示有交点)

但是这种原理的前提是两个链表要是相同的长度的,所以这变我们此时就要把链表的长度先给求出来(然后让更长的那个链表先走x步,走到最后跟较短的那个链表的长度一样,然后开始比较)

3.头结点就是头结点,不能乱给它移动位置,所以都是用一个cur去迭代找尾


1.故事理解代码:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //你是一个农村出身的穷小伙,她是一个一线城市的富家女,你爱上了她,你们的故事就此开始...
    //如果你们两没有遇见对方,此生无缘
    if (!headA || !headB)
        return NULL;
    int lengthA = 0;
    int lengthB = 0;
    struct ListNode *pA = headA;
    struct ListNode *pB = headB;
    //这是你目前的实力
    while(pA->next != NULL){
        pA = pA->next;
        lengthA++;
    }
    //这是她目前的实力
    while(pB->next != NULL){
        pB = pB->next;
        lengthB++;
    }
    //富家女的父亲和你谈话,摆明了你和她目前的差距是天与地,好让你认清现实,放弃他女儿
    int mid = lengthA - lengthB;
    struct ListNode *ppA = headA;
    struct ListNode *ppB = headB;
    //但是你不肯放手,想要与命运搏一搏,所以日以继夜的充实自己,追赶者她的步伐
    while (mid > 0){
        ppA = ppA->next;
        mid--;
    }
    while (mid < 0){
        ppB = ppB->next;
        mid++;
    }
    //你不断努力,终于把你和她之间的差距缩小到了最小
    //然后你们领了证,开始了婚后的平淡生活
    while( ppA != ppB){ //结局1 : 结婚后,诸多因素导致了你与她产生了嫌隙,最终,你们不欢而散
        ppA = ppA->next;
        ppB = ppB->next;
    }
    return ppA; //结局2 : 一直到最后你们仍旧和以前一样相濡以沫,走完了这一生,恭喜!
}

2.理论理解代码:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //这个题目的重点就是如何理解交点:要明白交点就是在同一位置时相等的点叫交点,不是相等就是交点,一定要是同一个位置才算是交点,所以假如链表长度不同,怎么可能在多余的地方找到交点
    struct ListNode *tailA=headA;
    struct ListNode *tailB=headB;
    //此时有了这两个尾指针我就要开始找尾了(然后进行尾的比较,如果尾的位置都不相同,那么就肯定不相交,因为根据图或者原理,可以知道只要这个是一个相交的链表那么尾肯定是相交的)
    //并且此时为了可以方便后面的计算,我们这边可以顺便把链表的长度给计算一下
    int lenA=1;
    while(tailA)
    {
        lenA++;
        tailA=tailA->next;
    }
    int lenB=1;
     while(tailB)
    {
        lenB++;
        tailB=tailB->next;
    }
    if(tailA!=tailB)
    {
        return NULL;
    }
    int gab=abs(lenA-lenB);//这个位置也可以使用三目操作符
     struct ListNode*longlist=headA;
      struct ListNode*shortlist=headB;
      if(lenA<lenB)
      {
          longlist=headB;
          shortlist=headA;
      }
    while(gab)//就是为了让我的末尾的位置对齐,才可以进行比较
    {
        longlist=longlist->next;
        gab--;
    }
    //此时程序来到这个位置就是说明我的链表是一样长的了
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
  //程序来到这个位置,自然而然的是说明我此时地址的位置相等,自然就是找到了相交的位置了
    return longlist;
}


相关文章
|
17天前
|
存储
链表题目练习及讲解(下)
链表题目练习及讲解(下)
23 9
|
17天前
链表题目练习及讲解(上)
链表题目练习及讲解(上)
22 1
|
11天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
16 0
|
16天前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
16天前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
17天前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
12 0
|
17天前
|
算法 Java
数据结构与算法学习六:单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例,详细讲解了约瑟夫环问题的解决方案,并提供了Java代码实现。
12 0
|
17天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
17 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
17天前
初步认识栈和队列
初步认识栈和队列
43 10
|
11天前
数据结构(栈与列队)
数据结构(栈与列队)
13 1