龙岩做网站龙岩网页设计_搜狗网址_2024年最新时事新闻_深圳网络营销渠道

坚持按题型打卡&刷&梳理力扣算法题系列，语言为go，Day13

链表的中间结点

• 题目描述
  
• 解题思路
  • 快慢指针
• 代码参考

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func middleNode(head *ListNode) *ListNode {slow := headfast := headfor fast != nil && fast.Next != nil{slow = slow.Nextfast = fast.Next.Next}return slow
}

• tips
  • 快慢指针的规律
  • 最开始的时候，快慢指针均指向头节点head
  • 当链表长度为奇数的时候，若快指针指向最后一个节点，则慢指针一定指向中间节点
  • 当链表长度为偶数时，当快指针指向空，则慢指针一定指向中间节点
  • 综上所述，当快指针指向空，或者快指针的下一个节点指向空的时候，则退出循环

环形链表

• 题目描述
  
• 解题思路
  • 快指针和慢指针相遇了，则说明存在环形链表（即链表中有环）
• 代码参考

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func hasCycle(head *ListNode) bool {slow := headfast := headfor fast != nil && fast.Next != nil{slow = slow.Nextfast = fast.Next.Nextif slow == fast{return true}}return false
}

• tips
  • 如果无环就不会无限循环，有环在循环中快慢会相遇

环形链表2

• 题目描述
  
• 解题思路
  • 先判断链表是否有环，并找到相遇点，然后利用规律，同时移动慢指针和头节点，两者的相遇处即为入口处
• 代码参考

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func detectCycle(head *ListNode) *ListNode {slow := headfast := headfor fast != nil && fast.Next != nil{slow = slow.Nextfast = fast.Next.Nextif fast == slow{for slow != head{head = head.Nextslow = slow.Next}return slow}}return nil
}

• tips
  • a-c = k（b+c）
    • slow从相遇点出发，head从头节点出发，走c步后，slow在入口，head到入口的距离也恰好是环长的倍数，所以两者必然会在入口相遇！
    • 这样就找到入口了