2012 年第 42 题

题目描述

两个单词分别采用带头结点的单链表存储。当两个单词有相同后缀时，可以共享相同的后缀存储空间。给定两个头指针 str1 和 str2，请找出这两个链表共同后缀的起始位置。

例如：

loading
being

共同后缀为 ing，对应共同起始结点是字符 i

解题思路

这题本质上就是“找两个链表的第一个公共结点”。

做法：

1. 分别求两个链表的长度。
2. 让较长链表先走若干步，直到两链表剩余长度相同。
3. 然后两个指针同步后移。
4. 第一次相遇的结点就是共同后缀的起点。

因为共同后缀在内存中是共享结点，所以判断依据是“结点地址相同”，不是字符相同。

手算示例

str1: l -> o -> a -> d -> i -> n -> g
str2: b -> e -> i -> n -> g

长度分别为 7 和 5，差值为 2
先让 str1 多走 2 步：

str1: a -> d -> i -> n -> g
str2: b -> e -> i -> n -> g

同步后移：
a vs b，不同
d vs e，不同
i vs i，且地址相同

答案：字符 i 对应的结点

Python 实现

class CharNode:
    def __init__(self, ch="", next=None):
        self.ch = ch
        self.next = next


def list_length_with_head(head):
    length = 0
    cur = head.next
    while cur:
        length += 1
        cur = cur.next
    return length


def common_suffix_start(str1, str2):
    len1 = list_length_with_head(str1)
    len2 = list_length_with_head(str2)

    p1 = str1.next
    p2 = str2.next

    if len1 > len2:
        for _ in range(len1 - len2):
            p1 = p1.next
    else:
        for _ in range(len2 - len1):
            p2 = p2.next

    while p1 and p2:
        if p1 is p2:
            return p1
        p1 = p1.next
        p2 = p2.next

    return None

复杂度分析

• 时间复杂度：O(m + n)
• 空间复杂度：O(1)

易错点

• 判断共同后缀时比较的是结点地址，不是字符值。
• 真题是带头结点链表，求长度时应从 head.next 开始。
• 长度对齐后再同步走，这是这题的关键。

对应题

来源	题目	相似度	主要差异
LeetCode	160. 相交链表	90%	真题为字符链表共同后缀
剑指 Offer	52. 两个链表的第一个公共节点	90%	真题为带头结点链表

难度

⭐️⭐️