[数据结构与算法]链表的相交和带环问题详解

判断链表是否相交

思路:如果两个链表的最后一个节点是同一个节点,那一定相交
注意:这里不是值相等就是同一个节点.
这个代码我就不敲了,比较简单,而且求交点的代码里面有

求两个相交链表的交点

//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //判断链表是否为空
    if(headA==NULL||headB==NULL)
    {
        return NULL;
    }
    //判断是否相交
    struct ListNode* cura=headA;
    struct ListNode* curb=headB;
//注意,int sizea,sizeb=1;  这种写法会默认sizea是0,导致错误
    int sizea=1;
    int sizeb=1;
    while(cura->next)
    {
        cura=cura->next;
        sizea++;
    }
    while(curb->next)
    {
        curb=curb->next;
        sizeb++;
    }
    if(cura!=curb)
    {
        return NULL;
    }

    //相交 长链表先走
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;
    int gap=sizea-sizeb;
    if(gap>0)
    {
        while(gap)
        {
            curA=curA->next;
            gap--;
        }
    }
    else
    {
        while(gap)
        {
            curB=curB->next;
            gap++;
        }
    }
while(curA!=curB)
    {
        curA=curA->next;
        curB=curB->next;
    }
    return curA;


}

判断链表是否带环

方法:快慢指针
主要分析:
快指针为什么一次走两步慢指针一次走一步,如果是快指针一次走三步走四步可不可以?
不可以
因为快指针一次走两步与慢指针的步数差是1,而一个环最小的节点数是2,就不会发生每次快指针都恰好绕过一圈而导致的快慢指针不相遇的问题

画一个简单的图来看,如果快指针一次走三步,就会恰好每次都错过慢指针

下面是代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
   
    //用快慢指针,快指针一次两步,慢指针一次一步,带环一定相遇
    struct ListNode* fast=head;
    struct ListNode* low=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        low=low->next;
        if(fast==low)
        {
            return true;
        }
    }
    return false;
    
}

求带环链表的环入口点

方式一:
从相遇点的位置将环断开,就转化成求两个链表交点问题,最后不要忘记将环合上.
方式二:
(这是大佬的方法,让我们一起学习一下)

下图是这个方法的证明过程,比较复杂需要画图理解,有点像数学几何的思想,仔细看这个过程,不复杂只是很巧妙!

下面是方式二的代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode node;
node* hascycle(node*head)
{
    node* fast=head;
    node* low=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        low=low->next;
        if(fast==low)
        {
            return fast;
        }
    }
    return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) {
    if(head==NULL)
    {  
        return NULL;
    }
    node* pm=hascycle(head);
    node* ph=head;
    if(pm==NULL)
    {
        return NULL;
    }
        while(pm!=ph)
        {
            pm=pm->next;
            ph=ph->next;
        }
        return pm;
}

链表这里有很多需要理解的地方,可能很多人觉得链表的算法比较难,实际上是因为对链表的理解和应用还是不够深入,多练习,多思考每一个算法,其实几天下来就拿下链表了!!加油!!!