160. 相交链表

已解答

简单

相关标签

相关企业

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 

# Definition for singly-linked list.

# class ListNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution(object):

    def getIntersectionNode(self, headA, headB):

        """

        :type head1, head1: ListNode

        :rtype: ListNode

        """

        # A, B = headA, headB

        # while A != B:

        #     A = A.next if A else headB

        #     B = B.next if B else headA

        # return A

        pa = headA

        pb = headB

        while pa!=pb:

         

            if pa==None:

                pa=headB

            else:

                pa=pa.next

            if pb==None:

                pb=headA

            else:

                pb=pb.next

        return pa

       

       

这个是因为两个链表，不论相交不相交，如果我们在遍历玩了一条之后去找另一条，那么长度是固定的也就是m+n+1（+1是因为到最后有个null也要遍历）。

如果相交，那么会到达相交的地方

如果不相交会到达null也会变成一样