力扣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;
}
目录
相关文章
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
1月前
|
存储
实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)
实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)
140 38
|
4天前
【力扣】21. 合并两个有序链表
【力扣】21. 合并两个有序链表
|
1月前
|
存储 JavaScript
leetcode82. 删除排序链表中的重复元素 II
leetcode82. 删除排序链表中的重复元素 II
22 0
|
1月前
leetcode83. 删除排序链表中的重复元素
leetcode83. 删除排序链表中的重复元素
10 0
|
1月前
leetcode2807.在链表中插入最大公约数
leetcode2807.在链表中插入最大公约数
16 0
|
1月前
leetcode2487.从链表中移除节点
leetcode2487.从链表中移除节点
20 1
|
1月前
|
存储 算法
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)
|
22天前
|
机器学习/深度学习 算法
力扣刷题日常(一)
力扣刷题日常(一)
20 2
|
1月前
|
存储 索引
《LeetCode》—— LeetCode刷题日记
《LeetCode》—— LeetCode刷题日记