leetcode面试题2.07

  • 方法一:暴力解法
    暴力解法,双层循环,唯一要注意的地方是每一次要给内层循环归零循环
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headB==nil||headA==nil{
        return nil
    }
    nodeb := headB
    for headA!=nil{
        nodeb = headB
        for nodeb!=nil{
            if headA==nodeb{
                return headA
            }
            nodeb = nodeb.Next
        }
        headA = headA.Next
    }
    return nil
}
  • 方法二:
    B指针移到与A末尾对齐的位置
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // AB 长度
    lena := 0
    lenb := 0
    // fast前进步数
    step := 0
    // 快慢指针
    fast := &ListNode{}
    slow := &ListNode{}
    // 求长度的时候用的临时节点
    node := &ListNode{}
    // 求A长度
    node = headA
    for node!=nil{
        lena++
        node = node.Next
    }
    // 求B长度,别忘了初始化
    node = headB
    for node!=nil{
        lenb++
        node = node.Next
    }
    // 判断AB长度哪个长,然后给长的赋值fast节点,
    // 同时计算出fast要前进的距离
    if lena>lenb{
        step = lena - lenb
        fast, slow = headA, headB
    }else{
        step = lenb - lena
        fast, slow = headB, headA
    }
    // fast前进
    for i:=0;i<step;i++{
        fast = fast.Next
    }
    // 只要fast!=slow,就一直循环,最后return
    for fast!=slow{
        fast  = fast.Next
        slow = slow.Next
    }
    return slow
}

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:459645 人次
ICP备案号: 辽ICP备20003309号