160.-intersection-of-two-linked-lists.md

160. Intersection of Two Linked Lists

{% tabs %} {% tab title="CPP" %}

/**
 * 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 *pa = headA;
        ListNode *pb = headB;

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

{% endtab %}

{% tab title="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:
        node_set = set()
        pA, pB = headA, headB
        while pB:
            node_set.add(pB)
            pB = pB.next
    
        while pA:
            if pA in node_set:
                return pA
            pA = pA.next
        return None
    
# 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:
        # linkedlist 相交肯定之多长为短链表.
        # 
        p1, p2 = headA, headB
        
        while p1 != p2:
            if p1 is not None :
                p1 = p1.next
            else:
                p1 = headB
            
            if p2 is not None:
                p2 = p2.next
            else:
                p2 = headA
                
            # 触发else的时候就是短的走完了,到长的走
            # 再触发保证等长
            
        return p1
        
        

{% endtab %} {% endtabs %}