160. 相交链表

多花时间微笑，少花时间蹙眉，多花时间表扬，少花时间批评。

题目

LC每日一题，参考160. 相交链表，题目要求使用时间复杂度 O(m + n) 、仅用 O(1) 内存。

解题思路

• 枚举：长的先走几部走到和短的链表相同长度的位置，然后直接比较是否相等。时间复杂度O(m+n+max(m,n))。
• 双指针：此方法比较巧妙，简单说就是两个指针走完自己的链表后继续走对面的链表，因为相当于：走完不同的a+相同部分+继续走b = 走完不同的b+相同部分+继续走a，长度相等所以两个指针会相遇。

枚举 解法

class Solution {
    fun getIntersectionNode(headA:ListNode?, headB:ListNode?):ListNode? {
        if(headA == null || headB == null) return null
        var ha = headA; var hb = headB
        var m = 0; var n = 0
        while(ha != null) {
            m ++
            ha = ha.next
        }
        while(hb != null) {
            n ++
            hb = hb.next
        }
        var len1 = m - n; var len2 = n - m
        ha = headA; hb = headB
        while(len1-->0) ha = ha?.next
        while(len2-->0) hb = hb?.next
        while(ha != hb) {
            ha = ha?.next
            hb = hb?.next
        }
        return ha
    }
}

复杂度分析

• 时间复杂度：O(m+n+max(m,n))，m/n分别为两个链表的长度。
• 空间复杂度：O(1)，只使用常量个变量。

双指针 解法

我们终归会相遇，据说此解法感动了无数人。

class Solution {
    fun getIntersectionNode(headA:ListNode?, headB:ListNode?):ListNode? {
        if(headA == null || headB == null) return null
        var ha = headA; var hb = headB
        while(ha != hb) {
            ha = if(ha == null) headB else ha.next
            hb = if(hb == null) headA else hb.next
        }
        return ha
    }
}

复杂度分析

• 时间复杂度：O(m+n)。
• 空间复杂度：O(1)。

2023.10.9