###### tags: `Leetcode` `easy` `list` `python` `c++` `Top 100 Liked Questions`

# 160. Intersection of Two Linked Lists

## [題目出處:] https://leetcode.com/problems/intersection-of-two-linked-lists/

## 題目:
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

[圖片來源]:https://leetcode.com/problems/intersection-of-two-linked-lists/

## 解題想法:
**將長度合併找交集處:**
以example1為例
A : 4 1 8 4 5 **5 6 1 8 4 5**
B : 5 6 1 8 4 5 **4 1 8 4 5**
相交處為8(因為共享記憶體位址)

## Python:

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        stack=[]
        while head:
            stack.append(head.val)
            head=head.next
        print(stack)

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        #用指針 a 指向 headA ，用指針 b 指向 headB
        h1 = headA
        h2 = headB
        
        #當 a 不等於 b 的時候，一直進行 while 循環，兩個鏈表同時向後遍歷，
        #如果 a 不為空則繼續下後遍歷一個節點，如果 a 為空則讓 a 指針指向 headB 
        #如果 b 不為空則繼續下後遍歷一個節點，如果 b 為空則讓 b 指針指向 headA
        while h1 != h2:
            if not h1:
                h1 = headB
            else:
                h1 = h1.next
            
            if not h2:
                h2 = headA
            else:
                h2 = h2.next
        #因為第一次遍歷"消除了兩個鏈表之間的長度差"
        #所以如果兩者相交，在第二次遍歷的時候肯定能找到 a == b 的節點，
        #如果兩者不相交，則 a 和 b 的遍歷結果肯定都為 None
        return h1
        

if __name__ == '__main__':
    listA=ListNode(4)
    listA.insert(1)
    listA.insert(8)
    listA.insert(4)
    listA.insert(5)

    listB=ListNode(5)
    listB.insert(6)
    listB.insert(1)
    listB.next.next.next=listA.next.next 

    result = Solution()
    ans = result.getIntersectionNode(listA,listB)
    print(ans.val)

## C++:

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(nullptr) {}
};

void InsertNode(ListNode *head, int data){
    ListNode *tail=head;
    if (tail->next)
        InsertNode(tail->next, data);
    else{
        ListNode *new_data= new ListNode(data);
        tail->next = new_data;
    }
}

void PrintList(ListNode* head){
    ListNode *tail=head;
    vector<int> res;
    while (tail){
        res.push_back(tail->val);
        tail=tail->next;
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

class Solution{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){
        ListNode *h1=headA;
        ListNode *h2=headB;

        while (h1 != h2){
            if (h1!=nullptr)
                h1=h1->next;
            else
                h1=headB;
            if (h2!=nullptr)
                h2=h2->next;
            else
                h2=headA;
        }
        return h1;
    }
};

int main(){
    ListNode *listA = new ListNode(4);
    InsertNode(listA,1);
    InsertNode(listA,8);
    InsertNode(listA,4);
    InsertNode(listA,5);
    cout<<"listA: ";
    PrintList(listA);

    ListNode *listB = new ListNode(5);
    InsertNode(listB,6);
    InsertNode(listB,1);
    listB->next->next->next=listA->next->next;

    cout<<"listB: ";
    PrintList(listB);

    Solution res;
    ListNode *ans=res.getIntersectionNode(listA,listB);
    cout<<ans->val;

    return 0;

}