160. Intersection of Two Linked Lists

molyzzx 发布于2019-08-14 14:16 / 2875人阅读

摘要：题目解答非常聪明的解法，因为两个的长度不一样，所以它让两个指针通过两次循环，来把两个都扫一遍。因为公共的部分相同，所以当它们相遇的时候，就是。

题目：
Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

解答：

public class Solution {
    //非常聪明的解法，因为两个linkedlist的长度不一样，所以它让两个指针通过两次循环，
    //来把两个linkedlist都扫一遍。因为公共的部分相同，所以当它们相遇的时候，就是intersection。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        
        ListNode a = headA;
        ListNode b = headB;
        
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        
        return a;
    }
}

云服务器 GPU云服务器 Intersection Lists linked two

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

转载请注明本文地址：https://www.ucloud.cn/yun/64913.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] Intersection of Two Linked Lists 链表交点

摘要：但是统计交点到终点的步数比较困难，我们可以直接统计从最短链表开头到交点的步数，其实是等价的。双指针法复杂度时间 O(N) 空间 O(1) 思路先算出两个链表各自的长度，然后从较长的链表先遍历，遍历到较长链表剩余长度和较短链表一样时，用两个指针同时遍历两个链表。这样如果链表有交点的话，两个指针已经一定会相遇。代码 public class Solution { publ...

andycall 2019-08-14 12:29 评论0 收藏0
[LintCode/LeetCode] Intersection of Two Linked Lis

Problem Write a program to find the node at which the intersection of two singly linked lists begins. Example The following two linked lists: A: a1 → a2 ↘ ...

OldPanda 2019-08-14 15:19 评论0 收藏0