LeetCode160—Intersection of Two Linked Lists

小咪咪 2022-07-15 12:26 115阅读 0赞

## 原题 ##

[原题链接][Link 1]

> 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.

--------------------

## 分析 ##

两个链表，可能有公共节点，也可能没有，如果有，找出这个公共节点。

### 解法1 ###

比较朴素的解法，遍历一遍链表A，遍历过后标记该节点为已访问，用`unordered_set`表示visit  
遍历B，如果遍历到某个节点发现在visit里面已经访问过，则说明该节点是公共节点，否则返回NULL。

这个解法的时间复杂度是O(m\+n)，无序集合（unordered\_set）查找、插入具有常数的时间复杂度。

class Solution {
    private:
        unordered_set<ListNode*> visit;
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            ListNode *p=headA;
            ListNode *r=headB;
    
            while(p!=NULL)
            {
                visit.insert(p);
                p=p->next;
            }
    
            while(r!=NULL)
            {
                if(visit.find(r)==visit.end())
                    r=r->next;
                else
                    break;
            }
            return r;
    
        }
    };

### 解法2 ###

使用unordered\_set虽然方便且有不错的时间效率，但是需要额外空间。题目后面要求到O(1)的空间复杂度。

下面这个算法非常巧妙，参考：[https://discuss.leetcode.com/topic/38444/simple-c-solution-5-lines/6][https_discuss.leetcode.com_topic_38444_simple-c-solution-5-lines_6]

class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
            {
            ListNode *pa=headA;
            ListNode *pb=headB;
            while(pa!=pb)
            {
                pa=pa?(pa->next):headB;
                pb=pb?(pb->next):headA;
            }
            return pa;
    
        }
    };

[Link 1]: https://leetcode.com/problems/intersection-of-two-linked-lists/
[https_discuss.leetcode.com_topic_38444_simple-c-solution-5-lines_6]: https://discuss.leetcode.com/topic/38444/simple-c-solution-5-lines/6