LeetCode160. 相交链表

今天药忘吃喽~ 2021-09-27 00:12 337阅读 0赞

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

例如，下面的两个链表：  
![这里写图片描述][70]

在节点 c1 开始相交。

注意：

如果两个链表没有交点，返回 null.  
在返回结果后，两个链表仍须保持原有的结构。  
可假定整个链表结构中没有循环。  
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解题思路：  
1.找到两个链表长度差n后较长的链表先走n步  
2,然后两个指针同时向前走，如果两个指针相等，则该点为交点的入口  
3.如果遍历完指针仍然不相等，则说明无焦点。

/** * 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 p1 = headA;
            ListNode p2 = headB;
            while (p1!=null&&p2!=null){
                p1=p1.next;
                p2=p2.next;
            }
            while (p1!=null){
                headA=headA.next;
                p1=p1.next;
            }
            while (p2!=null){
                headB=headB.next;
                p2=p2.next;
            }
            while (headA!=null&&headB!=null){
                if(headA==headB){
                    return headA;
                }
                headA=headA.next;
                headB=headB.next;
            }
            return null;
        }
    }

[70]: /images/20210923/b907b5145ee3405787e819defa700762.png

发表评论取消回复

表情：

评论列表（有 0 条评论，337人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode 160. 相交链表

《剑指 Offer》 [52. 两个链表的第一个公共节点][52.] 文章目录 * 1. 辅助栈 * * 1.1 思路 * 1.2 复杂...

àì夳堔傛蜴生んèń/ 2024年04月17日 05:35/ 0 赞/ 73 阅读

相关 LeetCode 160. 相交链表 JAVA

编写一个程序，找到两个单链表相交的起始节点。如下面的两个链表：在节点 c1 开始相交。

古城微笑少年丶/ 2022年12月09日 11:51/ 0 赞/ 150 阅读

相关【链表】 LeetCode160. 相交链表

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

绝地灬酷狼/ 2022年12月02日 13:38/ 0 赞/ 192 阅读

相关【LeetCode 160】相交链表

题目描述编写一个程序，找到两个单链表相交的起始节点。如下面的两个链表： ![在这里插入图片描述][20200817234343911.png] 在节点 c1 开

谁借莪１个温暖的怀抱￠/ 2022年11月28日 13:36/ 0 赞/ 168 阅读

相关 160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。图示两个链表在节点 c1 开始相交：

矫情吗；*/ 2022年10月18日 00:57/ 0 赞/ 214 阅读

相关 leetcode 160. 相交链表(python)

【前言】 python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/

冷不防/ 2022年05月19日 13:41/ 0 赞/ 165 阅读

相关 LeetCode【160.相交链表】

题目描述 > 编写一个程序，找到两个单链表相交的起始节点。 > > -------------------- > > 例如： > A: a1 → a2 > \

浅浅的花香味﹌/ 2022年05月08日 12:26/ 0 赞/ 194 阅读

相关 leetcode:160. 相交链表

题目: 编写一个程序，找到两个单链表相交的起始节点。如下面的两个链表：在节点 c1 开始相交。示例 1：输入：intersectVal = 8, list

r囧r小猫/ 2022年03月12日 12:27/ 0 赞/ 204 阅读

相关 LeetCode160.链表相交

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

旧城等待，/ 2022年02月19日 07:15/ 0 赞/ 284 阅读

相关 LeetCode160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。例如，下面的两个链表： ![这里写图片描述][70] 在节点 c1 开始相交。注意：如果两个链表没有交点，返回 n

今天药忘吃喽~/ 2021年09月27日 00:12/ 0 赞/ 338 阅读