[LintCode/LeetCode] Intersection of Two Linked Lis

OldPanda 發(fā)布于2019-08-14 15:19 / 3466人閱讀

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的起點(diǎn)。

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;
    }
}

云服務(wù)器 GPU云服務(wù)器 Intersection linked LIS python lis

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65611.html

相關(guān)文章

[LintCode/LeetCode] Intersection of Two Arrays I &

摘要：先想到的是，其實(shí)也可以，只是需要在遍歷的時(shí)候，添加到數(shù)組中的數(shù)要掉，略微麻煩了一點(diǎn)。在里跑的時(shí)候，也要快一點(diǎn)。另一種類似做法的就快的多了。如果是找出所有包括重復(fù)的截距呢 Problem Given two arrays, write a function to compute their intersection. Notice Each element in the result m...

enda 2019-08-14 14:03 評(píng)論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 2019-08-14 15:21 評(píng)論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區(qū)別...

tain335 2019-08-26 10:28 評(píng)論0 收藏0
[LintCode/LeetCode] Merge Two Sorted Lists

摘要：先考慮和有無空集，有則返回另一個(gè)。新建鏈表，指針將和較小的放在鏈表頂端，然后向后遍歷，直到或之一為空。再將非空的鏈表放在后面。 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 2019-08-14 15:22 評(píng)論0 收藏0
160. Intersection of Two Linked Lists

摘要：題目解答非常聰明的解法，因?yàn)閮蓚€(gè)的長度不一樣，所以它讓兩個(gè)指針通過兩次循環(huán)，來把兩個(gè)都掃一遍。因?yàn)楣驳牟糠窒嗤?，所以?dāng)它們相遇的時(shí)候，就是。題目：Write a program to find the node at which the intersection of two singly linked lists begins. For example, the followin...

molyzzx 2019-08-14 14:16 評(píng)論0 收藏0