LeetCode：160. Intersection of Two Linked Lists(找出两个链表的交点)

墨蓝 2022-04-11 12:12 119阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。
> 
> 这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方法1：

python实现方式1：

源码地址

--------------------

### 题目描述： ###

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表**：**

![format_png][]

在节点 c1 开始相交。

--------------------

### java实现方法1： ###

/**
         * 判断两个链表是否有交点
         *
         * @param headA 链表A
         * @param headB 链表B
         * @return 返回相交点
         */
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            ListNode pA = headA, pB = headB;
            while (pA != pB) {
                pA = pA == null ? headB : pA.next;
                pB = pB == null ? headA : pB.next;
            }
            return pA;
        }

时间复杂度：O(M +N)

空间复杂度：O(1)

--------------------

### python实现方式1： ###

def get_intersection_node(self, head_a: ListNode, head_b: ListNode) -> ListNode:
            '''
                返回交点
            Args:
                head_a: 链表a
                head_b: 链表b
            Returns:
                交点
            '''
            if not head_a or not head_b:
                return None
            p_A = head_a
            p_B = head_b
            while p_A != p_B:
                p_A = head_b if not p_A else p_A.next
                p_B = head_a if not p_B else p_B.next
            return p_A

时间复杂度：O(M + N)

空间复杂度：O(1)

--------------------

### 源码地址 ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[format_png]: /images/20220411/d3b9d1e4cdae4437bd640806b23a8961.png
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode