剑指Offer[52]-两个链表的第一个公共节点

题目

    4 - 1 
             \
                8 - 4 - 5
             /
5 - 0 - 1
  • 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
  • 输出:Reference of the node with value = 8
  • 输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

注意:

  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

python代码

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        def getLen(head):
            out_len = 1
            temp_head = head
            while temp_head.next:
                temp_head = temp_head.next
                out_len+=1
            return out_len

        if not (headA and headB):
            return None
        len_a = getLen(headA)
        len_b = getLen(headB)
        if len_a>=len_b:
            for i in range(len_a-len_b):
                headA = headA.next
        else:
            for i in range(len_b-len_a):
                headB = headB.next
        while headA and headB:
            if headA == headB:
                return headA
            else:
                headA = headA.next
                headB = headB.next

这道题采用双指针的思路,分别从两个链表开始,直到相遇(若存在交点)。

  • 考虑特殊情况
        # 当至少存在一个空链表,则直接返回None
        if not (headA and headB):
            return None
  • 获取两个链表的长度
        def getLen(head):
            out_len = 1
            temp_head = head
            while temp_head.next:
                temp_head = temp_head.next
                out_len+=1
            return out_len
        ....
        len_a = getLen(headA)
        len_b = getLen(headB)
  • 确定双指针各自的起点
        if len_a>=len_b:
            for i in range(len_a-len_b):
                headA = headA.next
        else:
            for i in range(len_b-len_a):
                headB = headB.next

这个很好理解,比如题目中的例子,在交点之前,链表A有两个节点,链表B有三个节点,所以我们就让链表B的指针起始位置放在第二个节点,这样双指针同步前进时,若存在交点,则它们一定会在交点相遇。

  • 双指针同步前进,在交点相遇
        while headA and headB:
            if headA == headB:
                return headA
            else:
                headA = headA.next
                headB = headB.next

发表评论

电子邮件地址不会被公开。