[面试题] 从职场监控到算法思路：解析“劝退”事件与相交链表双解法

最近在云栈社区上看到一个帖子：当事人描述自己因不同意公司的“劝退”方案，结果被安排到会议室单独办公，并且公司还专门安装了两个摄像头对准他，进行全天候监控。

评论区里的网友观点也各不相同，有人认为公司有权进行工作场所监管，有人则认为这已经构成了职场霸凌，还有不少人建议当事人立即收集证据，申请劳动仲裁。

在我看来，问题的关键或许不在于摄像头本身，而在于这种措施是否具有针对性、是否旨在制造精神压力从而迫使员工主动离职。如果整个办公室只有你一个人被如此“特殊关照”，那么其意图就相当明显了。

面对这种情况，与其情绪化对抗，不如先保持冷静，系统性地收集好所有相关证据——包括书面通知、调岗记录、监控环境等，然后咨询专业法律人士，明确自己可以争取的合法权益和补偿。

算法题：相交链表

相交链表这个问题，可以想象成两条道路：起始段各自独立，但在某个路口之后，它们汇合成同一条路，后续的路段完全共享。题目的核心就是找到这个汇合的路口。如果两条路始终没有交汇，则返回空。

翻译成编程问题：给你两个单链表的头节点 headA 和 headB，这两个链表可能在某个节点开始“合并”，后续节点共享；需要注意的是，这里要求的是节点的内存地址相同（对象相同），而不仅仅是节点存储的数值相同。你需要返回那个相交的节点，如果不相交则返回 None。

最朴素的想法是暴力比对：遍历链表A的每一个节点，再遍历链表B的所有节点，检查是否有地址相同的节点。这种方法的时间复杂度高达 O(m*n)，在链表较长时完全不可行。

另一种思路是使用一个 set 集合：先将链表A的所有节点地址存入集合，再遍历链表B，检查当前节点是否在集合中。这种方法时间复杂度为 O(m+n)，但需要 O(m) 的额外空间。

题目通常要求实现 时间复杂度 O(m+n)，空间复杂度 O(1) 的解法，这就需要一些巧妙的技巧了。

思路一：先计算长度，让长的链表先走

这是一个非常直观的方法：

1. 首先分别遍历两个链表，计算出各自的长度 lenA 和 lenB。
2. 让指向较长链表的指针先向前移动 |lenA - lenB| 步，使得两个指针距离各自链表尾部的长度相同。
3. 然后两个指针同步每次前进一步，它们第一次指向同一个节点时，那个节点就是交点；如果同时走到 None，则说明不相交。

核心思想在于：调整两个指针的“起跑线”，使它们距离终点（尾部）的剩余路程相同，这样它们就能在交点处相遇。

用 Python 实现如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def get_length(head: ListNode) -> int:
    length = 0
    cur = head
    while cur:
        length += 1
        cur = cur.next
    return length

def getIntersectionNode_len(headA: ListNode, headB: ListNode) -> ListNode | None:
    if not headA or not headB:
        return None

    lenA = get_length(headA)
    lenB = get_length(headB)

    curA, curB = headA, headB

    # 让较长的链表的指针先走几步
    if lenA > lenB:
        diff = lenA - lenB
        for _ in range(diff):
            curA = curA.next
    else:
        diff = lenB - lenA
        for _ in range(diff):
            curB = curB.next

    # 同步前进，寻找第一个相同的节点
    while curA is not curB:
        curA = curA.next
        curB = curB.next

    return curA  # 可能是交点，也可能是 None

这个方法逻辑清晰，只是多写了一个求链表长度的辅助函数。

思路二：双指针“互换路径”法，代码更简洁

这是一个经典且巧妙的双指针技巧，初次见到时往往让人豁然开朗。

思路如下：

• 指针 pA 从 headA 开始遍历，当它走到链表 A 的末尾（None）时，立即跳转到链表 B 的头部（headB） 继续遍历。
• 指针 pB 从 headB 开始遍历，当它走到链表 B 的末尾（None）时，立即跳转到链表 A 的头部（headA） 继续遍历。
• 两个指针每次都只前进一步。
• 如果两个链表相交，那么 pA 和 pB 必定会在相交节点相遇；如果不想交，那么它们最终会同时变为 None，循环也会终止。

为什么一定会相遇？我们可以简单计算一下两个指针走过的总路程：

• pA 的路程 = 链表 A 非公共部分 + 链表 B 非公共部分 + 公共部分（如果相交）
• pB 的路程 = 链表 B 非公共部分 + 链表 A 非公共部分 + 公共部分（如果相交）

可以看到，两个指针走过的总长度是相等的。因此，只要存在交点，它们必定会在某一时刻同步走到那个节点上。

实现代码非常简洁：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode | None:
    if not headA or not headB:
        return None

    pA, pB = headA, headB

    # 最多遍历两轮（m+n），要么在交点相遇，要么在 None 相遇
    while pA is not pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA

    return pA  # 或者 pB，此时它们相同

这种写法的优点很明显：

• 时间复杂度：每个指针最多遍历两个链表各一次，总体 O(m+n)。
• 空间复杂度：只使用了固定数量的指针变量，O(1)。
• 代码简洁：非常适合在面试的白板上书写。

我们可以构造一个简单的示例来验证：

def build_demo():
    # 公共部分：8 -> 9
    common1 = ListNode(8)
    common2 = ListNode(9)
    common1.next = common2

    # 链表 A：1 -> 2 -> 3 -> 8 -> 9
    a1 = ListNode(1)
    a2 = ListNode(2)
    a3 = ListNode(3)
    a1.next = a2
    a2.next = a3
    a3.next = common1

    # 链表 B：4 -> 5 -> 8 -> 9
    b1 = ListNode(4)
    b2 = ListNode(5)
    b1.next = b2
    b2.next = common1

    return a1, b1

if __name__ == "__main__":
    headA, headB = build_demo()
    node = getIntersectionNode(headA, headB)
    if node:
        print("相交点的值：", node.val)
    else:
        print("两个链表不相交")

运行上述代码，输出结果为：

相交点的值： 8

以上就是关于“相交链表”这道经典题目的两种核心解法。关键在于理解题目要求的“节点相同”是对象地址相同，而非值相同，并掌握通过调整指针起点或互换遍历路径来消除长度差的思想。在日常刷题练习时，将两种方法都实现一遍，有助于加深理解。