[数据结构与算法] 链表其他链表技巧 160. Intersection of Two Linked Lists (Easy)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 链表其他链表技巧 160. Intersection of Two Linked Lists (Easy) -> 正文阅读

[数据结构与算法]链表其他链表技巧 160. Intersection of Two Linked Lists (Easy)

首先的思路是看A和B在相交前差几个点，多的那个就先走，然后同步走，比较节点是否相等

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int counta = 0, countb = 0;
        ListNode *cura = headA, *curb = headB; 
        while(cura){
            cura = cura->next;
            counta++;
        }
        while(curb){
            curb = curb->next;
            countb++;
        }
        cura = headA;
        curb = headB;
        if(counta > countb){
            int diff = counta-countb;
            while(diff--){
                cura = cura->next;
            }
        }
        else{
            int diff = countb-counta;
            while(diff--){
                curb = curb->next;
            }
        }
        while(cura && curb){
            if(cura == curb){
                return cura;
            }
            cura = cura->next;
            curb = curb->next;
        }
        return nullptr;
    }
};

设A走到相交点距离是a，B走到相交点距离是b，相交点到终点距离是c，如果他们都走了a+b+c就会相遇，因此A走到终点时换到B头继续走，B一样，最后就会在相交点相遇。
情况二：两个链表不相交

链表 \textit{headA}headA 和 \textit{headB}headB 的长度分别是 mm 和 nn。考虑当 m=nm=n 和 m \ne nm

?
=n 时，两个指针分别会如何移动：

如果 m=nm=n，则两个指针会同时到达两个链表的尾节点，然后同时变成空值 \text{null}null，此时返回 \text{null}null；

如果 m \ne nm

?
=n，则由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，因此两个指针都会遍历完两个链表，在指针 \textit{pA}pA 移动了 m+nm+n 次、指针 \textit{pB}pB 移动了 n+mn+m 次之后，两个指针会同时变成空值 \text{null}null，此时返回 \text{null}null。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *l1 = headA, *l2 = headB;
            while (l1 != l2) {
                l1 = l1? l1->next: headB;
                l2 = l2? l2->next: headA;
            }
            return l1;
    }
};