[Leetcode] Intersection of Two Linked Lists 链表交点

andycall 发布于2019-08-14 12:29 / 1507人阅读

摘要：但是统计交点到终点的步数比较困难，我们可以直接统计从最短链表开头到交点的步数，其实是等价的。

双指针法 复杂度

时间 O(N) 空间 O(1)

思路

先算出两个链表各自的长度，然后从较长的链表先遍历，遍历到较长链表剩余长度和较短链表一样时，用两个指针同时遍历两个链表。这样如果链表有交点的话，两个指针已经一定会相遇。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodea = headA, nodeb = headB;
        int lena = 0, lenb = 0;
        // 计算链表A的长度
        while(nodea != null){
            lena++;
            nodea = nodea.next;
        }
        // 计算链表B的长度
        while(nodeb != null){
            lenb++;
            nodeb = nodeb.next;
        }
        // 让较长的链表先飞一会
        for(int i = 0; i < Math.abs(lena - lenb); i++){
            if(lenb > lena) headB = headB.next;
            else if(lena > lenb) headA = headA.next;
        }
        while(headA != null && headB != null){
            if(headA == headB) return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

后续 Follow Up

Q：如果是K个链表的交点如何求？
A：先找出K个链表中长度最短的那个，然后用同样的方法将其他链表和这个链表两两比较，因为每个都有可能有一个不同的交点，所以我们要维护一个全局最优的交点，更新这个全局最优交点的条件，是这个交点到终点的步数是最少的。但是统计交点到终点的步数比较困难，我们可以直接统计从最短链表开头到交点的步数，其实是等价的。

GPU云服务器云服务器 Intersection Lists linked 直线交点

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64504.html

LeetCode 160：相交链表 Intersection of Two Linked List

摘要：示例输入输出输入解释相交节点的值为注意，如果两个列表相交则不能为。解释这两个链表不相交，因此返回。注意如果两个链表没有交点，返回在返回结果后，两个链表仍须保持原有的结构。此时将指向链表长链表的头节点，不变。爱写Bug（ID：iCodeBugs）编写一个程序，找到两个单链表相交的起始节点。 Write a program to find the node at which the i...

wing324 2019-08-16 18:38 评论0 收藏0
LeetCode 160：相交链表 Intersection of Two Linked List

摘要：示例输入输出输入解释相交节点的值为注意，如果两个列表相交则不能为。解释这两个链表不相交，因此返回。注意如果两个链表没有交点，返回在返回结果后，两个链表仍须保持原有的结构。此时将指向链表长链表的头节点，不变。爱写Bug（ID：iCodeBugs）编写一个程序，找到两个单链表相交的起始节点。 Write a program to find the node at which the i...

ormsf 2019-07-31 11:29 评论0 收藏0
Intersection of 2 lists

摘要：得到个链条的长度。将长的链条向前移动差值两个指针一起前进，遇到相同的即是交点，如果没找到，返回空间复杂度，时间复杂度 Intersection of Two Linked ListsWrite a program to find the node at which the intersection of two singly linked lists begins. For examp...

thursday 2019-08-14 17:10 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
JAVASCRIPT算法（6）

摘要：还是链表算法题目描述给出两个无环单链表判断和是否相交。所以可以得出另外一种解法，先遍历链表，记住尾节点，然后遍历链表，比较两个链表的尾节点，如果相同则相交，不同则不相交。想法还是奇妙的。算法写起来不难，难的是想到这个。还是链表算法题目描述：给出两个无环单链表A: a1 → a2 ↘ c1 → c2 → c3 → ...

FreeZinG 2019-08-21 17:56 评论0 收藏0