leetcode链表（五）-链表相交

题目

. - 力扣（LeetCode）

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

图示两个链表在节点 c1 开始相交：

 

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 0 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

思路

• 先分别统计出两个链表的长度lenA和lenB，并求出两个链表的长度差
• 将长的那个链表先移动长度差的长度的位置，即让两个链表从tail处对齐

例如例题中的

以tail结尾对齐就是

分别让两个指针从当前位置向后移动，移动一步判断一次两个节点是否相等，要是相等就返回这个节点，要是到尾都没有相等的，那就是两个链表无交点，返回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:
        if not headA or not headB:
            return None
        lenA,lenB = 0,0
        pheadA,pheadB = ListNode(next=headA),ListNode(next=headB)
        while pheadA:
            lenA+=1
            pheadA = pheadA.next
        while pheadB:
            lenB+=1
            pheadB = pheadB.next

        sub = abs(lenA-lenB)
        pheadA,pheadB = ListNode(next=headA),ListNode(next=headB)
        if lenB > lenA:
            pheadB,pheadA = pheadA,pheadB
        for _ in range(sub):
            pheadA = pheadA.next
        for _ in range(min(lenA,lenB)):
            if pheadA == pheadB:
                return pheadA
            else:
                pheadA = pheadA.next
                pheadB = pheadB.next
        return None
            

原文地址：https://blog.csdn.net/weixin_40198632/article/details/142884143

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！