第四十四天

找出链表的倒数第N个节点。如何判断链表有环?

对于链表的问题，我们可以分别解答：

1. 找出链表的倒数第N个节点：

// 定义链表节点结构
type ListNode struct {
    Val  int
    Next *ListNode
}

// 找到链表的倒数第N个节点
func findNthFromEnd(head *ListNode, n int) *ListNode {
    // 创建两个指针，p1和p2，初始时它们都指向链表头
    p1, p2 := head, head

    // p2先向前移动n个节点
    for i := 0; i < n && p2 != nil; i++ {
        p2 = p2.Next
    }

    // 如果n大于链表长度，p2会为nil，此时返回nil
    if p2 == nil {
        return nil
    }

    // p1和p2同时向前移动，直到p2到达链表尾部
    for p2.Next != nil {
        p1, p2 = p1.Next, p2.Next
    }

    // 此时p1指向的就是倒数第n个节点
    return p1
}

2. 判断链表是否有环：

// 判断链表是否有环，使用快慢指针方法
func hasCycle(head *ListNode) bool {
    slow, fast := head, head

    // 快指针每次移动两步，慢指针每次移动一步
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        // 如果快慢指针相遇，则链表有环
        if slow == fast {
            return true
        }
    }

    // 没有相遇则链表无环
    return false
}

这两个函数分别实现了寻找链表倒数第N个节点和判断链表是否有环的功能。在实际应用中，可以根据链表的节点结构和链接情况进行适配。

分库分表如何设计? 场景: 例如本订单表是按照id进行的分表, 但是有的查询, 需要根据id进行查询, 有的查询需要根据活动id查询, 如何实现这个分表方案?

在设计分库分表方案时，面对既需要按照ID分表，又需要支持按照活动ID查询的场景，可以采用以下几种策略：

1. 哈希分片（Hash-based Sharding）：

   • 对于按照ID分表，可以使用哈希分片的方式，例如取模（Hash(id) % N）来决定数据落在哪张表或哪个数据库中。但是这种方式无法直接满足按照活动ID查询的需求。

2. 范围分片（Range-based Sharding）：

   • 如果活动ID与订单ID有一定的关联性，例如活动ID可以映射到一定范围的订单ID，那么可以按照订单ID的范围来进行分表，但这需要活动ID的分配有一定的规律。

3. 复合分片（Composite Sharding）：

   • 垂直分片：将与活动ID强相关的字段放在一个单独的表或分片中，而订单的基础信息（包括ID）放在另一个表或分片中。查询时，根据需要分别查询两个表，然后在应用层合并结果。
   • 水平分片：对订单表进行复合分片，可以基于订单ID进行第一次分片，然后再在每个分片的基础上，根据活动ID做第二次分片。但这意味着分表策略会变得复杂，且需要额外的路由逻辑来定位数据。

4. 二级索引表（Secondary Index Table）：

   • 创建一个活动ID到订单ID的映射表，并在该表上建立索引，该表存储的是活动ID和对应的订单ID列表。当需要按照活动ID查询时，先查询映射表，然后再根据得到的订单ID列表去各个分表中查询订单详情。

5. 全局索引服务：

   • 使用专门的全局索引服务，如Elasticsearch、Solr等，对活动ID建立索引，查询时通过索引服务获取到对应的订单ID列表，然后再到数据库中查询详细信息。

6. 分布式数据库中间件：

   • 使用分布式数据库中间件，如MyCat、ShardingSphere等，这些中间件可以提供透明的分片策略，并支持复杂的分片键组合，例如按照订单ID分片的同时，还能根据活动ID做二次路由查询。

综合考虑，实际应用中可能需要结合业务特性和数据访问模式，设计合理的分片策略，并可能结合索引服务、中间件等技术手段来优化查询性能。在设计时务必考虑到数据的一致性、扩展性和查询性能等方面的平衡。