力扣160:相交链表

简介: 力扣160:相交链表

力扣160:相交链表

题目描述:

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

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

题目数据 保证 整个链式结构中不存在环。


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


自定义评测:


评测系统 的输入如下(你设计的程序 不适用 此输入):


intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0

listA - 第一个链表

listB - 第二个链表

skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数

skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。


示例 1:

输入: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出: Intersected at ‘8’

示例 2:

输入: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1


输出: Intersected at ‘2’


502ef3574389f4eaa055e36eeca77147_7a5114a4e7b149b4bc92b316bffac25e.png


输入: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出: null


提示:


listA 中节点数目为 m

listB 中节点数目为 n

1 <= m, n <= 3 * 104

1 <= Node.val <= 105

0 <= skipA <= m

0 <= skipB <= n

如果 listA 和 listB 没有交点,intersectVal 为 0

如果 listA 和 listB 有交点,intersectVal == listA[skipA] == listB[skipB]


分析:


  1. 解法1:暴力求解

分别遍历链表A和链表B,找到两个链表地址相同的位置即可,但是时间复杂度很高,O(n2

  1. 解法2:
  • 分别找尾节点,并记录两个链表的长度
  • 如果尾节点的地址不一样,则说明没有公共交点。注意:是比较地址,不是比较值
  • 遍历两个链表,返回相同的节点即可:

(1)计算两个链表长度的差值,让长的链表先遍历,当长度一致时,再两个链表一起遍历。定义两个指针,一个指向较长的哪一个链表longlist,一个指向较短的链表shortlist.两个链表的长度我们不知道哪一个长哪一个短,因此需要先去判断,让较长的链表先遍历。这里有一个比较简便方法:用A链表的长度-B链表的长度,并取绝对值,假设链表A的长度较长,使longlist指向A链表的头节点headA,shortlist指向B链表的头节点headB。但是,这只是假设,实际情况不知道是怎样的。所以用一个if语句,如果链表A的长度小于链表B的长度,那么规定longlist为链表B的头节点headB,shortlist为链表A的头节点headB。


(2)先让长的先遍历。


(3)两个链表同时遍历,如果longlist=shortlist,说明两个链表的当前节点地址相同,表明此节点为交点,则停止遍历,最后返回这个节点即可。


代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*curA=headA,*curB=headB;
    int lenA=1,lenB=1;
    while(curA)
    {
        lenA++;
        curA=curA->next;
    }
    while(curB)
    {
        lenB++;
        curB=curB->next;
    }
    if(curA!=curB)
    {
        return NULL;
    }
    int gap=abs(lenA-lenB);
    struct ListNode*longlist=headA,*shortlist=headB;
    if(lenA<lenB)
    {
        longlist=headB;
        shortlist=headA;
    }
    while(gap--)
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
}
目录
相关文章
|
12月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
128 1
|
12月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
153 0
Leetcode第21题(合并两个有序链表)
|
4月前
|
机器学习/深度学习 算法
24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点 ,面试题 02.07. 链表相交
1. **两两交换链表中的节点**:通过引入虚拟头结点,使所有节点都能采用统一的交换逻辑,避免对头结点单独处理。 2. **删除链表的倒数第N个节点**:利用双指针技巧,让快慢指针保持N个节点的距离,当快指针到达末尾时,慢指针正好指向待删除节点的前一个节点。 3. **链表相交**:先计算两链表长度并调整起点,确保从相同距离末尾的位置开始遍历,从而高效找到相交节点或确定无交点。 以上方法均在时间复杂度和空间复杂度上进行了优化,适合用于理解和掌握链表的基本操作及常见算法设计思路。
|
6月前
|
算法 Go
【LeetCode 热题100】23:合并 K 个升序链表(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法:优先队列(最小堆)和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值,;分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码,并对比分析两种方法的适用场景,帮助读者深入理解链表操作与算法设计。
195 10
|
12月前
|
算法
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
91 1
|
12月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
125 0
LeetCode第二十四题(两两交换链表中的节点)
|
12月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
239 0
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
132 2