题目描述

最简单直接的解法

遍历 headA 的所有节点, 看 headB 中是否有相交的节点

/*** Definition for singly-linked list.* 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 next: ListNode? = headAwhile next != nil {if containNode(headB, next) {return next}next = next?.next}return nil
}func containNode(_ headB: ListNode?, _ node: ListNode?) -> Bool {var next: ListNode? = headBwhile next != nil {if node === next { return true }next = next?.next}return false
}
}

哈希集合优化

因为示例中的 ListNode 没有实现 Hash 相关协议, 所以无法使用 Set, 这里使用 Array 代替. (LeetCode, 咱能不能重视一下 Swift 用户, OK ?)

/*** Definition for singly-linked list.* public class ListNode {*     public var val: Int*     public var next: ListNode?*     public init(_ val: Int) {*         self.val = val*         self.next = nil*     }* }*/class Solution {var globalSet = Array<ListNode?>()func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {var next: ListNode? = headAif (globalSet.contains { $0 === next }) {return next}while next != nil {if containNode(headB, next) {return next}next = next?.next}return nil
}func containNode(_ headB: ListNode?, _ node: ListNode?) -> Bool {var next: ListNode? = headBwhile next != nil {if node === next { return true }if (!globalSet.contains { $0 === next }) {globalSet.append(next)}next = next?.next}return false
}}

上面两个方法提交后, 结果都是: 超出时间限制

双指针

/*** Definition for singly-linked list.* 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? {if headA == nil || headB == nil {return nil}var pA = headA, pB = headBwhile pA !== pB {pA = pA == nil ? headB : pA?.nextpB = pB == nil ? headA : pB?.next}return pA}
}