我命由我,不由天!


  • 搜索
prometheus docker golang linux kubernetes

链表相关

发表于 2021-05-04 | 0 | 阅读次数 428

链表结构体

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

环形链表一

给定一个链表,判断链表中是否有环。

  1. 使用快慢指针,快指针一次两步,慢指针一次一步。如果链表有环则快指针一定会追上慢指针
  2. 退出循环条件需要判断当前快指针是否为nil,和快指针的Next是否为nil。因为在循环体中需要用到,如果为nil会出现panic
func hasCycle(head *ListNode) bool {
    if head == nil {
        return false
    }
    for slow,fast := head,head.Next;fast != nil && fast.Next != nil ;{
        if slow == fast{
            return true
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return false
}

环形链表二

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

  1. 先判断有环,快指针和慢指针相遇(快指针速度为慢指针的两倍,则走过的路程也为两倍)
  2. 快指针到起点,然后以和慢指针相同的速度继续前进,当第二次相遇的时候就是入环的第一个节点
func detectCycle(head *ListNode) *ListNode {
   slow,fast := head,head
   for fast != nil && fast.Next !=nil{
       slow = slow.Next
       fast = fast.Next.Next
       if slow == fast{
           fast = head
           for {
               if fast == slow{
                   return fast
               }
               fast = fast.Next
               slow = slow.Next
           }
       }
   }
   return nil
}
  • 本文作者: Dante
  • 本文链接: https://gaodongfei.com/archives/链表
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
LRU
mysql时区问题
  • 文章目录
  • 站点概览
Dante

Dante

119 日志
5 分类
5 标签
RSS
Creative Commons
0%
© 2023 Dante
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
沪ICP备2020033702号