首页 > itarticle > intersection of two linked list

intersection of two linked list

admin 11月 11, 2020 0

描述

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

分析

分别计算出两个链表的长度，让较长的的链表头先往前挪相应的步数让两链表剩下的部分等长。然后两个指针同步向前，直到相遇（或者各自走到尾部）。

代码

Python

class (object):
    def getLength(self, node):
        n = 0
        while node:
            node = node.next
            n += 1
        return n

    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        n1 = self.getLength(headA)
        n2 = self.getLength(headB)
        pA = headA
        pB = headB
        if n1 > n2:
            for i in xrange(n1 - n2):
                pA = pA.next
        else:
            for i in xrange(n2 - n1):
                pB = pB.next
        while pA != pB:
            pA = pA.next
            pB = pB.next

        return pA