Intersection of 2 lists

thursday 发布于2019-08-14 17:10 / 2919人阅读

摘要：得到个链条的长度。将长的链条向前移动差值两个指针一起前进，遇到相同的即是交点，如果没找到，返回空间复杂度，时间复杂度

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

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

转载请注明本文地址：https://www.ucloud.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

摘要：题目解答非常聪明的解法，因为两个的长度不一样，所以它让两个指针通过两次循环，来把两个都扫一遍。因为公共的部分相同，所以当它们相遇的时候，就是。题目：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

摘要：示例输入输出输入解释相交节点的值为注意，如果两个列表相交则不能为。解释这两个链表不相交，因此返回。注意如果两个链表没有交点，返回在返回结果后，两个链表仍须保持原有的结构。此时将指向链表长链表的头节点，不变。爱写Bug（ID：iCodeBugs）编写一个程序，找到两个单链表相交的起始节点。 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

摘要：示例输入输出输入解释相交节点的值为注意，如果两个列表相交则不能为。解释这两个链表不相交，因此返回。注意如果两个链表没有交点，返回在返回结果后，两个链表仍须保持原有的结构。此时将指向链表长链表的头节点，不变。爱写Bug（ID：iCodeBugs）编写一个程序，找到两个单链表相交的起始节点。 Write a program to find the node at which the i...

ormsf 2019-07-31 11:29 评论0 收藏0