考研笔记

板子：两个链表的公共结点（2012）

两条链表从第一个公共结点开始，后面的结点全部共用，形状像字母 Y。所以公共部分一定在尾部：先让长的那条多走 步，把两边剩下的长度对齐，再一起往后走，第一次指向同一个结点的地方就是答案。

代码

int listLen(LinkList L) {                    // 表长，不算头结点
    int n = 0;
    for (LNode *p = L->next; p != NULL; p = p->next) n++;
    return n;
}
 
LNode *findCommon(LinkList str1, LinkList str2) {   // 2012：共同后缀的起始结点
    int m = listLen(str1), n = listLen(str2);
    LNode *p = str1, *q = str2;
    for (; m > n; m--) p = p->next;          // 长的那条先走 |m-n| 步，之后两边剩下的一样长
    for (; n > m; n--) q = q->next;          // 两个 for 只会有一个真正执行
    while (p != q) {                         // 比较的是地址：公共结点是同一个结点，不只是值相等
        p = p->next;
        q = q->next;
    }
    return p;                                // 没有公共结点时两边同时走到 NULL，返回 NULL
}

复杂度：时间 ，空间 。

例（2012 原题）：loading 和 being 共用后缀 ing，返回的是 i 那个结点。

易错点

  • 比较的是 p != q（地址），不是 p->data != q->data。两个单词里各有一个 i，但它们不一定是同一个结点。
  • 两条链表不可能交叉成 X 形：一个结点只有一个 next，一旦汇合就不会再分开。
  • 暴力解是对 str1 的每个结点都把 str2 扫一遍，，也是正确解。
  • 求表长不算头结点，两边口径一样就行，对齐的步数不受影响。

链接

反向链接