Leetcode 160. 相交链表

最新推荐文章于 2024-03-10 15:21:22 发布

斵冰且行

最新推荐文章于 2024-03-10 15:21:22 发布

阅读量191

点赞数

分类专栏：编程算法文章标签： Leetcode 剑指 Offer 链表

本文链接：https://blog.csdn.net/moonspiritacm/article/details/100022530

版权

编程算法专栏收录该内容

14 篇文章

订阅专栏

本文深入解析了《剑指Offer》中两个链表的第一个公共节点问题，提供了两种解决方案：一是使用辅助栈倒置链表，二是采用双指针策略消除长度差，最终高效地找到相交点。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

1. 辅助栈

1.1 思路

相交链表必成 Y 型，即头部分叉、尾部相同。因此，从尾部开始比对，直到找到最后一个相同的节点，即为链表的第一个公共节点。

利用辅助栈，将链表倒置，实现倒序比较。以空间换时间，在空间复杂度上还可以进一步优化。

1.2 复杂度

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

1.3 代码

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        while (headA != null) {
            s1.push(headA);
            headA = headA.next;
        }
        while (headB != null) {
            s2.push(headB);
            headB = headB.next;
        }
        ListNode root = null;
        while (!s1.isEmpty() && !s2.isEmpty() && s1.peek() == s2.peek()) {
            root = s1.pop();
            s2.pop();
        }
        return root;
    }
}

2. 双指针

2.1 思路

若两链表长度相同，从头开始逐节点比对，直到发现公共节点即可；若两链表长度不同，先消除长度差，再进行节点比对。

消除长度差的两种策略：

减去法：将长链表减去多出部分，使两链表长度相等，遍历直到发现公共节点；
加长法：长链表尾部接上短链表，短链表尾部接上长链表，使两链表长度相等，遍历直到出现公共节点。

在这里插入图片描述

2.2 复杂度

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

2.3 代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != null && curB != null) {
            curA = curA.next;
            curB = curB.next;
        }
        if (curA == null) {
            while (curB != null) {
                curB = curB.next;
                headB = headB.next;
            }
        } else {
            while (curA != null) {
                curA = curA.next;
                headA = headA.next;
            }
        }
        while (headA != null && headB != null && headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != curB) {
            curA = curA == null ? headB : curA.next;
            curB = curB == null ? headA : curB.next;
        }
        return curA;
    }
}