资讯专栏INFORMATION COLUMN

[LintCode/LeetCode] Intersection of Two Linked Lis

OldPanda / 3419人阅读

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
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Note

原理: A.length + Intersection + B.length = B.length + Intersection + A.length,也就是说,走了相同的三段长度之后,正好一起回到Intersection的起点。

Solution
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA, l2 = headB;
        while (l1 != l2) {
            l1 = l1 == null ? headB: l1.next;
            l2 = l2 == null ? headA: l2.next;
        }
        return l1;
    }
}

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

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

相关文章

  • [LintCode/LeetCode] Intersection of Two Arrays I &

    摘要:先想到的是,其实也可以,只是需要在遍历的时候,添加到数组中的数要掉,略微麻烦了一点。在里跑的时候,也要快一点。另一种类似做法的就快的多了。如果是找出所有包括重复的截距呢 Problem Given two arrays, write a function to compute their intersection. Notice Each element in the result m...

    enda 评论0 收藏0
  • [LintCode/LeetCode] Add Two Numbers

    Problem You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1s digit is at the head of the list. Write a f...

    hedzr 评论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 评论0 收藏0
  • [LintCode/LeetCode] Merge Two Sorted Lists

    摘要:先考虑和有无空集,有则返回另一个。新建链表,指针将和较小的放在链表顶端,然后向后遍历,直到或之一为空。再将非空的链表放在后面。 Problem Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splici...

    dockerclub 评论0 收藏0
  • 160. Intersection of Two Linked Lists

    摘要:题目解答非常聪明的解法,因为两个的长度不一样,所以它让两个指针通过两次循环,来把两个都扫一遍。因为公共的部分相同,所以当它们相遇的时候,就是。 题目:Write a program to find the node at which the intersection of two singly linked lists begins. For example, the followin...

    molyzzx 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<