判断两个单链表是否相交

文章转自: http://c.biancheng.net/data_structure/linear_list/

---

所谓相交，是指有公共的部分，而 2 个单链表相交，则意味着它们有公共的节点，公共节点的数量可以是 1 个或者多个。

单链表是线性表的一种，如果我们将 2 个单链表看做 2 条线段的话，下图则模拟了 2 条线段相交的所有可能情况。

结合“单链表中每个节点有且仅有 1 个指针域”的特性，上图所示的这 3 种情况中，只有第 2 种情况符合单链表的特性，另外 2 种情况则破坏了此特性。因此要验证 2 个单链表是否相交，实际上等同于判断 2 个单链表是否和② 所示的存储结构相同。

判断 2 个单链表（下文分别称它们为链表 1 和链表 2 ）是否相交，常用的方法有如下几种。

1. 方法一

分别遍历链表 1 和链表 2，对于链表 1 中的每个节点，依次和链表 2 中的各节点进行比对，查看它们的存储地址是否相同，如果相同，则表明它们相交；反之，如果链表 1 中各节点的存储地址，和链表 2 中的各个节点都不相同，则表明它们不相交。

假设定义的链表节点如下:

typedef struct Link 
{
    char elem; //代表数据域
    struct Link * next; //代表指针域，指向直接后继元素
}link; //link为节点名，每个节点都是一个 link 结构体
1
2
3
4
5

在此基础上，判断 2 个单链表是否相交的实现代码为：

//自定义的 bool 类型
typedef enum bool
{
    False = 0,
    True = 1
}bool;

//L1 和 L2 为 2 个单链表，函数返回 True 表示链表相交，返回 False 表示不相交
bool LinkIntersect(link * L1, link * L2) 
{
    link * p1 = L1;
    link * p2 = L2;
    //逐个遍历 L1 链表中的各个节点
    while (p1)
    {
        //遍历 L2 链表，针对每个 p1，依次和 p2 所指节点做比较
        while (p2) 
        {
            //p1、p2 中记录的就是各个节点的存储地址，直接比较即可
            if (p1 == p2) 
            {
                return True;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
    return False;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

通过分析 LinkIntersect() 函数的实现过程不难得知，无论 2 个链表是否相交，此实现方式的时间复杂度为O(n2)。

2. 方法二

实际上，第 1 种实现方法还可以进一步优化。结合图中②，2 个单链表相交有一个必然结果，即这 2 个链表的最后一个节点必定相同；反之，如果 2 个链表不相交，则这 2 个链表的最后一个节点必定不相同。

由此，可以对以上实现代码进行优化：

//L1 和 L2 为 2 个单链表，函数返回 True 表示链表相交，返回 False 表示不相交
bool LinkIntersect(link * L1, link * L2) 
{
    link * p1 = L1;
    link * p2 = L2;
    //找到 L1 链表中的最后一个节点
    while (p1->next) 
    {
        p1 = p1->next;
    }
    //找到 L2 链表中的最后一个节点
    while (p2->next)
    {
        p2 = p2->next;
    }
    //判断 L1 和 L2 链表最后一个节点是否相同
    if (p1 == p2) 
    {
        return True;
    }
    return False;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

经过优化后该函数的时间复杂度就缩小为O(n)。

3. 方法三

针对第 1 种实现方法的优化，除了第 2 种方式，还有一种思想。

假设 L1 和 L 2 相交，则两个链表中相交部分节点的数量一定是相等的。如下图所示：

可以看到，L1 和 L2 相交，绿色部分节点为 L1 和 L2 链表的相交部分。

也就是说，如果 2 个链表相交，那么它们相交部分所包含的节点个数一定相等。在此基础上，我们可以这样优化第 1 种实现方案，以上图中的 L1 和 L2 为例，从 L1 尾部选取和 L2 链表等长度的一个子链表（也也就是下图中的 temp 子链表），同时遍历 temp 和 L2 链表，依次判断 2 个遍历节点是否相同，如果相同则表明 L1 和 L2 相交；反之则不相交。

此实现方案的实现代码如下：

//L1 和 L2 为 2 个单链表，函数返回 True 表示链表相交，返回 False 表示不相交
bool LinkIntersect(link * L1, link * L2) 
{
    link * plong = L1;
    link * pshort = L2;
    link * temp = NULL;
    int num1 = 0, num2 = 0, step = 0;
    //得到 L1 的长度
    while (plong) 
    {
        num1++;
        plong = plong->next;
    }
    //得到 L2 的长度
    while (pshort)
    {
        num2++;
        pshort = pshort->next;
    }
    //重置plong和pshort，使plong代表较长的链表，pshort代表较短的链表
    plong = L1;
    pshort = L2;
    step = num1 - num2;
    if (num1 < num2) 
    {
        plong = L2;
        pshort = L1;
        step = num2 = num1;
    }
    //在plong链表中找到和pshort等长度的子链表
    temp = plong;
    while (step) 
    {
        temp = temp->next;
        step--;
    }
    //逐个比较temp和pshort链表中的节点是否相同
    while (temp && pshort) 
    {
        if (temp == pshort) 
        {
            return True;
        }
        temp = temp->next;
        pshort = pshort->next;
    }
    return False;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

相比第 2 种方案，此方法的实现逻辑虽然复杂，但优点是，该方法可以找到 2 个单链表相交的交点（也就是相交时的第一个节点），也就是使 LinkIntersect() 函数返回 True 时的 temp 指针指向的那个节点。另外，此方案的时间复杂度也为O(n)。

总结: 比较这 3 种方案，第 1 种和 第 3 种在判断“2 个链表是否相交”的同时，还能找到它们相交的交点，而第 2 种实现方案则不具备这个功能。