LeetCode160.相交链表

妖狐艹你老母 2023-10-09 13:48 48阅读 0赞

#### 文章目录 ####

*  LeetCode160.相交链表
 *   *  问题描述
     *  方法一
     *   *  算法思想
         *  动画演示
         *  代码演示
         *  算法分析
     *  方法二
     *   *  算法描述
         *  代码演示
         *  算法分析

## LeetCode160.相交链表 ##

### 问题描述 ###

给你两个单链表的头节点 **headA** 和 **headB** ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 **null** 。

**图示两个链表在节点 c1 开始相交：**

![在这里插入图片描述][064750c4d8384e03b8e91a1bca18abba.png]  
题目数据 保证 整个链式结构中**不存在环**。

注意，函数返回结果后，链表必须 **保持其原始结构** 。

### 方法一 ###

#### 算法思想 ####

使用**双指针**  
当两个链表headA和headB都不为null时，两个链表才可能相交，如果有一个链表为空，两个链表就不可能相交，所以首先应该判断两个链表是否为空，有一个为空，则返回null。  
如果两个链表都不为空，则创建两个指针pA和pB， 初始时两个指针分别指向两个链表的头结点headA和headB，然后将两个指针分别遍历两个链表的每个结点。  
**具体步骤如下：**  
**①**每步操作需要同时移动指针pA和pB。  
**②**如果指针pA不为空，将指针更新到下一个结点；如果指针pB不为空，将指针更新到下一个结点。  
**③**如果指针pA为空，则将指针pA移到链表headB的头结点；如果指针pB为空，则将指针pA移到链表headA；  
**④**当指针pA和pB指向同一个结点或者都为null时，循环结束，返回他们指向的**结点**或者**null**。

#### 动画演示 ####

![在这里插入图片描述][1de26f06e601451896af93098fabf309.gif]

#### 代码演示 ####

class ListNode {
        
        int val;
        ListNode next;
    
        ListNode(int x) {
        
            val = x;
            next = null;
        }
    }
    
    public class Solution {
        
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            if(headA == null || headB == null) {
        
                return null;
            }
    
            ListNode pA = headA;
            ListNode pB = headB;
            while(pA != pB) {
        
                pA = pA == null ? headB : pA.next;
                pB = pB == null ? headA : pB.next;
            }
            return pA;
        }
    }

#### 算法分析 ####

`时间复杂度` **O(m + n)**，其中 m 和 n 分别是链表headA和headB的长度。两个指针同时遍历两个链表，每个链表各被遍历一次。  
`空间复杂度` **O(1)**。

### 方法二 ###

#### 算法描述 ####

同方法一也是采用**双指针法**。  
当两个链表headA和headB有一个为null时，直接返回null。  
如果两个链表都不为空，**具体步骤如下：**  
**①**分别遍历两个链表，得到链表headA的长度**count1**，链表headB的长度**count2**。  
**②**创建两个指针p1和p2，比较**count1**和**count2**，使指针p1指向较长的链表，指针p2指向较短的链表。  
**③**计算两个链表的长度差diff，然后让指针p1先往后遍历diff个结点。  
**④**同时移动指针p1和p2。当指针p1和p2指向同一个结点或者都为null时，循环结束，返回他们指向的**结点**或者**null**。

#### 代码演示 ####

class ListNode {
        
        int val;
        ListNode next;
    
        ListNode(int x) {
        
            val = x;
            next = null;
        }
    }
    
    public class Solution {
        
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            if(headA == null || headB == null) {
        
                return null;
            }
    
            ListNode p1;
            ListNode p2;
    
            int count1 = 0;
            int count2 = 0;
            for(ListNode p = headA; p != null;p = p.next) {
        
                count1++;
            }
    
            for(ListNode p = headB; p != null;p = p.next) {
        
                count2++;
            }
    
            p1 = count1 > count2 ? headA : headB;
            p2 = count1 > count2 ? headB : headA;
            int diff = Math.abs(count1 - count2);
            while(diff-- > 0) {
        
                p1 = p1.next;
            }
    
            while(p1 != p2) {
        
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        }
    }

#### 算法分析 ####

`时间复杂度` **O(m + n)**，其中 m 和 n 分别是链表headA和headB的长度。两个指针同时遍历两个链表，每个链表各被遍历一次。  
`空间复杂度` **O(1)**。

[064750c4d8384e03b8e91a1bca18abba.png]: https://img-blog.csdnimg.cn/064750c4d8384e03b8e91a1bca18abba.png
[1de26f06e601451896af93098fabf309.gif]: https://img-blog.csdnimg.cn/1de26f06e601451896af93098fabf309.gif

发表评论取消回复

表情：

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

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

相关阅读

相关 Leetcode 160. 相交链表

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

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

相关 LeetCode160.相交链表

文章目录 LeetCode160.相交链表问题描述方法一算法思想动画演示

妖狐艹你老母/ 2023年10月09日 13:48/ 0 赞/ 49 阅读

相关 leetcode160 相交链表

![20191202203256532.png][] 编写一个程序，找到两个单链表相交的起始节点。如下面的两个链表： ![2019120220365978.png][]

叁歲伎倆/ 2023年06月18日 13:55/ 0 赞/ 48 阅读

相关 Leetcode 160. 相交链表

Leetcode 160. 相交链表 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.c

- 日理万妓/ 2023年02月14日 03:00/ 0 赞/ 15 阅读

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

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

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

相关【LeetCode 160】相交链表

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

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

相关 LeetCode【160.相交链表】

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

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

相关 leetcode:160. 相交链表

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

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

相关 LeetCode160.链表相交

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

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

相关 LeetCode160. 相交链表

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

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