Leetcode question brushing series - mode 2 (datastructure linked list) - 160:intersection of two linked list

leetcode Brush questions series ---- Pattern 2（Datastructure Linked list ）- 160：Intersection of Two Linked List Intersecting list

Tips

• For more information, please refer to the catalogue of this series
• This linked list problem can be solved by using double pointers , Note that the complexity of the algorithm is O(m+n), signify 2*（m+n） Second traversal also belongs to the time complexity , We should not think narrowly that we only traverse m+n Secondary linked list node .
• Double pointers are really a big class of algorithmic ideas .

Python

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        pointA = headA
        pointB = headB
        if not pointA or not pointB: return None
        while pointA != pointB:
            if pointA: pointA = pointA.next
            else: pointA = headB
            if pointB: pointB = pointB.next
            else: pointB = headA
        return pointA

C++

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    
        ListNode* pointA = headA;
        ListNode* pointB = headB;
        if (pointA==nullptr || pointB==nullptr) return nullptr;
        while (pointA!=pointB)
        {
    
            if(pointA!=nullptr) pointA=pointA->next;
            else pointA=headB;
            if(pointB!=nullptr) pointB=pointB->next;
            else pointB=headA;
        }
        return pointA;
        
    }
};

C#

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */
public class Solution {
    
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
    
        ListNode pointA = headA;
        ListNode pointB = headB;
        if (pointA==null || pointB==null) return null;
        while (pointA!=pointB)
        {
    
            if(pointA!=null) pointA=pointA.next;
            else pointA=headB;
            if(pointB!=null) pointB=pointB.next;
            else pointB=headA;
        }
        return pointA;
    }
}

Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        ListNode pointA = headA;
        ListNode pointB = headB;
        if (pointA==null || pointB==null) return null;
        while (pointA!=pointB)
        {
    
            if(pointA!=null) pointA=pointA.next;
            else pointA=headB;
            if(pointB!=null) pointB=pointB.next;
            else pointB=headA;
        }
        return pointA;        
    }
}