[LintCode/LeetCode] Intersection of Two Linked Lis

OldPanda 發布于2019-08-14 15:19 / 3456人閱讀

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

GPU云服務器云服務器 Intersection linked LIS python lis

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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 2019-08-14 14:03 評論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 評論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
[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 2019-08-14 15:22 評論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 2019-08-14 14:16 評論0 收藏0