求两个链表的交点

# 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
        """
        if headA is None or headB is None:
            return None

        head1 = self.reverseList(headA)
        head2 = self.reverseList(headB)
        # iterator pointer
        it1 = head1
        it2 = head2
        if it1.val != it2.val:
            return None
        it0 = it1
        while it1 and it2:
            if it1.val == it2.val:
                it0 = it1
                it1 = it1.next
                it2 = it2.next
            else:
                return it0
        return it0

    def reverseList(self, head):
        # 边界处理
        if head is None:
            return None
        if head.next is None:
            return head

        #  从第二个节点开始处理
        prev = head
        cur = head.next

        while cur is not None:
            future = cur.next
            cur.next = prev
            prev = cur
            cur = future
        # 第一个节点
        head.next = None
        return prev

最后

以上就是生动冰棍最近收集整理的关于求两个链表的交点的全部内容，更多相关求两个链表内容请搜索靠谱客的其他文章。