Day7 . 面试题 02.07. 链表相交

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/

核心思想：双指针

• 链表A：1 → 2 → 3 → 8 → 4 → 5

• 链表B：6 → 7 → 8 → 4 → 5
  （相交节点是值为8的节点）

• ​步骤1​：数得A长度=6，B长度=5。

• ​步骤2​：A更长，把A的指针从第1个节点移到第2个节点（6-5=1步），现在A从2开始，B从6开始，剩余长度都是5。

• ​步骤3​：A和B一起往后走，走到第4步时，A指向8，B也指向8，返回这个节点。

# 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:
        lenA,lenB = 0,0

        #计算链表A和B的长度
        cur = headA
        while cur:
            cur=cur.next
            lenA += 1
        cur = headB
        while cur:
            cur=cur.next
            lenB += 1
        
        curA,curB = headA,headB

        # 交换指针，让lenB永远最长，减少代码冗余if else
        if lenA>lenB:
            curA,curB =curB,curA
            lenA,lenB = lenB,lenA

        
        for _ in range(lenB-lenA):
            curB = curB.next

        while curA:
            if curA == curB:
                return curA
            else:
                curA = curA.next
                curB = curB.next
        return None