LeetCode算法题：链表相交

这是无量测试之道的第224篇原创

题目描述

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第 k 个节点与另一个链表的第 j 个节点是同一节点（引用完全相同），则这两个链表相交。

输入：listA = [4,2,8,4,5,6], listB = [5,0,1,8,4,5] 输出：[8,4,5]

核心思路:

你变成我，我变成你，我们便相遇了。那么为什么能相遇呢？ 设长链表 A 长度为 LA，短链表长度 LB；由于速度相同，则在长链表 A 走完 LA 长度时，短链表 B 已经反过头在 A 上走了 LA-LB 的长度，剩余要走的长度为 LA-(LA-LB) = LB； 之后长链表 A 要反过头在 B上走，剩余要走的长度也是 LB；也就是说目前两个链表“对齐”了。因此，接下来遇到的第一个相同节点便是两个链表的交点。 那如果两个链表不存在交点呢？ 答：这样的话第 4 步就会一直执行到两个链表的末尾，la,lb 都为 null,也会跳出循环，返回null。

代码如下:

public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
    }
}

class Solution {
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
var currentA = headA
var currentB = headB
//！等价于 同一对象
while currentA.val != currentB.val {
        currentA = (currentA != nil) ? currentA?.next : headB
        currentB = (currentB != nil) ? currentB?.next : headA
      }
return currentA
    }
}

今天分享的不容易想到，但是很巧妙。自己想，可能一会儿很难想到，所以平时需要多刷刷题。

end