题目介绍

题目链接

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
题目考点

链表、双指针
题目难度

LeetCode简单
题目大意

给定2个链表，请找出它们的相交结点。

读题可知：两个指针相同（并不是2个结点的值相同）即需要求得的结果，2个链表的长度不确定，2个链表可能没有相交结点，链表中无循环。
输入

2个链表的头指针
输出

相交结点的指针

题解一

解题思路

双指针法

假如2个链表有交叉点（intersection），则可以设这2个链表彼此不重复的结点分别为d1和d2，重复的结点为d，即链表A=d1+d、链表B=d2+d。如果1个链表遍历完则使其从另外1个链表的头部重新开始，形成2条长度相等的路径：d1+d+d2, d2+d+d1，这2条路径走完之后2个指针就刚好遍历到相交结点。如果这2个链表没有交叉点，那最后2个指针都正好是空。
复杂度分析

假设2个链表的结点数分别为n和m，则时间复杂度为$O(n+m)$、空间复杂度为$O(1)$。这个思路是该题效率最高的算法。

代码

// Problem: Leetcode 160
// URL: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
// Tags: Linked List
// Difficulty: Easy

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){
        // Deal with the border "nullptr"
        if (nullptr==headA || nullptr==headB)
        {
            return nullptr;
        }
        ListNode *ptrA = headA;
        ListNode *ptrB = headB;
        
        // d1+d+d2=d2+d+d1
        while (ptrA != ptrB){
            ptrA = nullptr == ptrA ? headB : ptrA->next;
            ptrB = nullptr == ptrB ? headA : ptrB->next;
        }
        return ptrA;
    }
};

题解二

暴力枚举法

写2层循环，外循环遍历链表A，内循环遍历链表B并判断此时链表A的当前结点是否与链表B中某个结点相同。
复杂度分析

假设2个链表的结点数分别为n和m，则时间复杂度为$O(nm)$、空间复杂度为$O(1)$。

代码略

题解三

哈希法

遍历链表A，将每个结点都放在哈希表中（可以用unordered_set，它底层就是哈希表。我看很多题解里用的set，它的底层不是哈希表而是二叉树），然后遍历链表B找到第1个在哈希表中的结点。
复杂度分析

假设2个链表的结点数分别为n和m，则平均时间复杂度为$O(n+m)$、空间复杂度为$O(m)$或$O(n)$。

代码略

题解四

栈法

将2个链表的结点压入栈中，然后弹栈找到最后1个相同结点，即为要找的相交节点。
复杂度分析

假设2个链表的结点数分别为n和m，则最小时间复杂度为$O(n+m)$、最大时间复杂度为$O(n+m+max(n,m))$、空间复杂度为$O(m+n)$。

参考链接

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!