Intersection of 2 lists

thursday 發(fā)布于2019-08-14 17:10 / 2924人閱讀

摘要：得到個鏈條的長度。將長的鏈條向前移動差值兩個指針一起前進，遇到相同的即是交點，如果沒找到，返回空間復雜度，時間復雜度

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個鏈條的長度。

將長的鏈條向前移動差值（len1 - len2）

兩個指針一起前進，遇到相同的即是交點，如果沒找到，返回null.

空間復雜度O(1)，時間復雜度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;
        }
    }

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

轉載請注明本文地址：http://systransis.cn/yun/66462.html

[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 2019-08-14 15:45 評論0 收藏0
[Algo] Find Intersection of Two Sets 找交集

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

pf_miles 2019-08-14 12:43 評論0 收藏0
160. Intersection of Two Linked Lists

摘要：題目解答非常聰明的解法，因為兩個的長度不一樣，所以它讓兩個指針通過兩次循環(huán)，來把兩個都掃一遍。因為公共的部分相同，所以當它們相遇的時候，就是。題目：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
LeetCode 160：相交鏈表 Intersection of Two Linked List

摘要：示例輸入輸出輸入解釋相交節(jié)點的值為注意，如果兩個列表相交則不能為。解釋這兩個鏈表不相交，因此返回。注意如果兩個鏈表沒有交點，返回在返回結果后，兩個鏈表仍須保持原有的結構。此時將指向鏈表長鏈表的頭節(jié)點，不變。愛寫B(tài)ug（ID：iCodeBugs）編寫一個程序，找到兩個單鏈表相交的起始節(jié)點。 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

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

ormsf 2019-07-31 11:29 評論0 收藏0