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

待我称王封你为后i 2023-01-13 10:20 56阅读 0赞

# 题目描述 #

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

链表节点定义如下：

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;
        }
    }

##### 复杂度分析： #####

*  **时间复杂度 O(a + b) ：** 最差情况下（即 |a - b| = 1，c = 0 ），此时需遍历 a + b个节点。
 *  **空间复杂度 O(1)：** 节点指针 `A` , `B` 使用常数大小的额外空间。