侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

52 两个链表的第一个公共节点

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 107 阅读 / 2,807 字 / 正在检测是否收录...

剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表,找出它们的第一个公共节点。

方法一:辅助栈

使用两个栈 $S1$ 和 $S2$ ,分别存储链表 $A$ 和 $B$,一开始将 $A$ 和 $B$ 都存入栈中。使用 ans 指向最终答案。

然后不断弹出,弹出的过程中,判断两个节点是否相等,如果相等则记录下来,$ans$ 指向相等的节点,然后继续弹出直到两个节点不相等,则 $ans$ 指向的节点就是最终答案。

代码:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Deque<ListNode> sA = new LinkedList<>();
    Deque<ListNode> sB = new LinkedList<>();
    putIntoStack(headA, sA);
    putIntoStack(headB, sB);
    ListNode ans = null;
    // 判断是否有共同节点
    boolean intersect = false;
    while (!sA.isEmpty() && !sB.isEmpty()) {
        ListNode a = sA.pop();
        ListNode b = sB.pop();
        if (a != b) {
            return ans;
        }
        intersect = true;
        ans = a;
    }
    return intersect ? ans : null;
}

private void putIntoStack(ListNode head, Deque<ListNode> stack) {
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
}

复杂度分析

  • 时间复杂度$O(MN)$:$M$、$N$ 分别为两个链表的长度。
  • 空间复杂度$O(MN)$:辅助栈最多要存储两个链表的所有节点。

方法二:快慢指针

先计算两条链表的长度,然后计算长度差 d,快指针现在先对较长的链表上走 d 步。然后慢指针在快指针走了 d 步后,两条指针同时走。

  • 如果快慢指针指向的节点相同,那么它是第一个公共节点;
  • 如果快慢指针直到走完都没有相等,那么不存在公共节点。

代码:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 比较两条链表的长度,得出二者的长度差值 d
    // 长的那条链表的指针先走 d 步,然后两个链表指针同时走,第一次相等时,就是第一相交节点
    int lenA = listLen(headA);
    int lenB = listLen(headB);
    ListNode smaller, bigger;
    smaller = lenA < lenB ? headA : headB;
    bigger = smaller == headA ? headB : headA;
    int diff = Math.abs(lenA - lenB);
    while (diff > 0) {
        bigger = bigger.next;
        diff--;
    }
    while (smaller != null && bigger != null) {
        if (smaller == bigger) {
            return smaller;
        }
        smaller = smaller.next;
        bigger = bigger.next;
    }
    return null;
}

private int listLen(ListNode head) {
    int ans = 0;
    while (head != null) {
        ans++;
        head = head.next;
    }
    return ans;
}

复杂度分析:

  • 时间复杂度$O(MN)$:$M$、$N$ 分别为两个链表的长度。
  • 空间复杂度$O(1)$:辅助变量占用常数大小的额外空间。

方法三:

假设链表 $A$ 的非公共长度为 $a$,链表 $B$ 的非公共长度为 $b$,二者的公共长度为 $c$。

52-abc

观察上图,如果先走完链表 $A$ 然后再走链表 $B$ 的 $b$ 部分,可以到达公共点。同样的,如果先走完链表 $B$ 然后再走链表 $A$ 的 $a$ 部分,可以达到公共点。关系如下:

$$ a + c + b = b + c + a $$

如果两个链表没有公共部分,即 $c = 0$,那么走完两条链表后,会指向 null

52-ab

关系如下:

$$ a + b = b + a $$

代码:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = a != null ? a.next : headB;
        b = b != null ? b.next : headA;
    }
    return a;
}

复杂度分析

  • 时间复杂度$O(MN)$:$M$、$N$ 分别为两条链表的长度。
  • 空间复杂度$O(1)$:辅助变量占用常数大小的空间。
0

评论区