当前位置：首页 > news >正文

剑指Offer系列（java版，详细解析）52.两个链表的第一个公共节点

news 来源：原创 2024/4/29 16:04:43

题目描述

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

链表节点定义如下：

public class ListNode {
    int value;
    ListNode next;
}

测试用例

功能测试（输入的两个链表有公共节点：第一个公共节点在链表的中间，第一个公共节点在链表的尾部，第一个公共节点是链表的头节点；输入的两个链表没有公共节点）
特殊输入测试（输入的链表头节点是空指针）

题目考点

考察应聘者对时间复杂度和空间复杂度的理解及分析能力。解决这道题有多种不同的思路。每当应聘者想到一种思路的时候，都要很快分析出这种思路的时间复杂度和空间复杂度各是多少，并找到可以优化的地方。
考察应聘者对链表的编程能力。

用栈解题

对于上面那张图，我们会想到我们只要从链表的尾部开始遍历。那么最后一个相同的节点就是我们要找的节点。但是单向链表不能从尾开始遍历，所以我们要借助栈来实现从尾部遍历。

这种算法：时间复杂度为O(m+n)，空间复杂度也是O(m+n)

参考解题

用栈解题

/**
 * 两个链表的第一个公共节点
 */
public class Solution {
    /**
     * 用栈解题
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode commonNode = null;
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        // JDK建议双向队列Deque优先于Stack
        Deque<ListNode> stack1 = new ArrayDeque<>();
        Deque<ListNode> stack2 = new ArrayDeque<>();
        // 两个链表入栈
        while (pHead1 != null) {
            stack1.push(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null) {
            stack2.push(pHead2);
            pHead2 = pHead2.next;
        }
        // 不断出栈比较
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek() == stack2.peek()) {
                commonNode = stack1.peek();
            }
            stack1.pop();
            stack2.pop();
        }
        return commonNode;
    }
}

规律解题

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    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;
    }
}