成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

Intersection of 2 lists

thursday / 3005人閱讀

摘要：得到個(gè)鏈條的長(zhǎng)度。將長(zhǎng)的鏈條向前移動(dòng)差值兩個(gè)指針一起前進(jìn)，遇到相同的即是交點(diǎn)，如果沒(méi)找到，返回空間復(fù)雜度，時(shí)間復(fù)雜度

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 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.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

SOLUTION 1:

得到2個(gè)鏈條的長(zhǎng)度。

將長(zhǎng)的鏈條向前移動(dòng)差值（len1 - len2）

兩個(gè)指針一起前進(jìn)，遇到相同的即是交點(diǎn)，如果沒(méi)找到，返回null.

空間復(fù)雜度O(1)， 時(shí)間復(fù)雜度O(m+n)

public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        int lenA = getLen(headA);
        int lenB = getLen(headB);
        
        if (lenA > lenB) {
            while (lenA > lenB) {
                headA = headA.next;
                lenA--;
            }
        } else {
            while (lenA < lenB) {
                headB = headB.next;
                lenB--;
            }
        }
        
        while (headA != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        
        return null;
    }
    
    public int getLen(ListNode node) {
        int len = 0;
        while (node != null) {
            len++;
            node = node.next;
        }
        return len;
    }

SOLUTION 2:
Two pointer solution (O(n+m) running time, O(1) memory):
Maintain two pointers pA and pB initialized at the head of A and B, respectively. Then let them both traverse through the lists, one node at a time.
When pA reaches the end of a list, then redirect it to the head of B (yes, B, that"s right.); similarly when pB reaches the end of a list, redirect it the head of A. The first iteration counteract the difference of len thus the meeting points of second iteration would be the intersection point. Return null if two lists are parallel.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        ListNode pA = headA;
        ListNode pB = headB;
        
        ListNode tailA = null;
        ListNode tailB = null;
        
        while (true) {
            if (pA == null) {
                pA = headB;
            }
            
            if (pB == null) {
                pB = headA;
            }
            
            if (pA.next == null) {
                tailA = pA;
            }
            
            if (pB.next == null) {
                tailB = pB;
            }
            
            //The two links have different tails. So just return null;
            if (tailA != null && tailB != null && tailA != tailB) {
                return null;
            }
            
            if (pA == pB) {
                return pA;
            }
            
            pA = pA.next;
            pB = pB.next;
        }
    }

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/66462.html

相關(guān)文章

  • [LeetCode] Intersection of Two Arrays I & II

    Intersection of Two Arrays I Problem Given two arrays, write a function to compute their intersection. Example Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2]. Note Each element in the result m...

    lucas 評(píng)論0 收藏0

  • [Algo] Find Intersection of Two Sets 找交集

    摘要：暴力法復(fù)雜度時(shí)間空間思路暴力解法，對(duì)于每個(gè)在集合中的元素，我們遍歷一遍集合看看是否存在，如果存在則是。代碼排序二分搜索復(fù)雜度時(shí)間空間思路將較短的那個(gè)集合排序，然后對(duì)于較長(zhǎng)的集合中每一個(gè)元素，都在較短的集合中二分搜索相應(yīng)的元素。 Find Intersection of Two Sets 暴力法 復(fù)雜度 時(shí)間 O(NM) 空間 O(1) 思路 暴力解法，對(duì)于每個(gè)在集合1中的元素，我們遍歷...

    pf_miles 評(píng)論0 收藏0

  • 160. Intersection of Two Linked Lists

    摘要：題目解答非常聰明的解法，因?yàn)閮蓚€(gè)的長(zhǎng)度不一樣，所以它讓兩個(gè)指針通過(guò)兩次循環(huán)，來(lái)把兩個(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 評(píng)論0 收藏0

  • LeetCode 160： 相交鏈表 Intersection of Two Linked List

    摘要：示例輸入輸出輸入解釋相交節(jié)點(diǎn)的值為注意，如果兩個(gè)列表相交則不能為。解釋這兩個(gè)鏈表不相交，因此返回。注意如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回在返回結(jié)果后，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。此時(shí)將指向鏈表長(zhǎng)鏈表的頭節(jié)點(diǎn)，不變。 愛(ài)寫(xiě)B(tài)ug（ID：iCodeBugs） 編寫(xiě)一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。 Write a program to find the node at which the i...

    wing324 評(píng)論0 收藏0

  • LeetCode 160： 相交鏈表 Intersection of Two Linked List

    摘要：示例輸入輸出輸入解釋相交節(jié)點(diǎn)的值為注意，如果兩個(gè)列表相交則不能為。解釋這兩個(gè)鏈表不相交，因此返回。注意如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回在返回結(jié)果后，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。此時(shí)將指向鏈表長(zhǎng)鏈表的頭節(jié)點(diǎn)，不變。 愛(ài)寫(xiě)B(tài)ug（ID：iCodeBugs） 編寫(xiě)一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。 Write a program to find the node at which the i...

    ormsf 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<