今日题目有：

  • 在排序数组中查找元素的第一个和最后一个位置
  • 环形链表
  • k个一组翻转链表

1. 在排序数组中查找元素的第一个和最后一个位置

题目描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为$ O(log_n) $的算法解决此问题。

示例：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

思路

有序数组并且查找复杂度要求$ O(log_n) $的复杂度，我们可以用二分查找来实现。 分别使用两次二分来查找左右边界，这里安利一个五点七边老师的二分讲解视频，使用这个模板再也不怕从入门到入睡了。

Swift实现

func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        let left = lowerBound(nums, target)
        let right = upperBound(nums, target)

        // 检查 target 是否在范围内
        if left <= right && right < nums.count && nums[left] == target && nums[right] == target {
            return [left, right]
        }
        return [-1, -1]
    }
    
    // 利用二分找左边界，想象一直缩小右边界，无限趋左
    // 即在 nums[mid] == target的时候，将right移到mid
    func lowerBound(_ nums: [Int], _ target: Int) -> Int {
        var left = -1, right = nums.count
        while left + 1 != right {
            let mid = left + (right - left) / 2
            if nums[mid] < target {
                left = mid
            } else {
                right = mid
            }
        }
        return right
    }
    
    // 找右边界
    func upperBound(_ nums: [Int], _ target: Int) -> Int {
        var left = -1, right = nums.count
        while left + 1 != right {
            let mid = left + (right - left) / 2
            if nums[mid] <= target {
                left = mid
            } else {
                right = mid
            }
        }
        return left
    }

2. 环形链表

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

思路

基础题，使用快慢指针来做。快指针每次前进2跳，满指针前进1跳。如果快慢指针相遇，则说明有环。（Floyd 判圈算法）

Swift实现

func hasCycle(_ head: ListNode?) -> Bool {
    var fast = head
    var slow = head
    while let f = fast, let fNext = fast?.next {
        slow = slow?.next
        fast = fNext.next
        if slow === fast {
            return true
        }
    }
    return false
}

3. k个一组翻转链表

题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路

链表题，习惯性用dummy node来辅助解题，先创建一个虚节点，其next指向head节点。 然后我们可以按组来处理链表，定义groupPrev标记待翻转组的前一个节点，对于每一个组，先找到第k个节点记为kNode,

然后翻转区间[groupPrev.next, kNode]之间的所有节点，这里可以使用原地迭代或者头插法，哪个顺手用哪个。 翻转完成后更新groupPrev.next和groupPrev。

循环所有组，知道无法凑成k个节点。

Swift实现

// 定义链表节点类
class ListNode {
    var val: Int
    var next: ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

// 辅助函数：从当前节点开始，返回第 k 个节点（k 个节点后为 nil 则返回 nil）
func getKthNode(_ current: ListNode?, _ k: Int) -> ListNode? {
    var curr = current
    var count = 0
    // 注意：这里从 current 开始向后数 k 次
    while curr != nil && count < k {
        curr = curr?.next
        count += 1
    }
    // 如果凑够了 k 个节点，则返回第 k 个节点；否则返回 nil
    return count == k ? curr : nil
}

// 主函数：每 k 个一组翻转链表
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
    // k==1 或空链表无需翻转，直接返回 head
    if k <= 1 || head == nil {
        return head
    }
    
    // 创建哑节点，并将其 next 指向 head
    let dummy = ListNode(0)
    dummy.next = head
    
    // groupPrev 表示当前组翻转前的前一个节点，初始时为 dummy
    var groupPrev: ListNode? = dummy
    
    // 循环处理每一组
    while true {
        // 获取当前组的第 k 个节点
        guard let kth = getKthNode(groupPrev, k) else {
            // 如果不足 k 个节点，直接退出循环
            break
        }
        // groupNext 是当前组后面的节点（翻转后需要接到组尾）
        let groupNext = kth.next
        
        // 开始翻转当前组内的节点
        // prev 初始化为 groupNext，原因是翻转后最后一个节点指向 groupNext
        var prev: ListNode? = groupNext
        var curr = groupPrev?.next  // 当前组第一个节点
        
        // 翻转链表：从 groupPrev.next 到 kth 节点
        while curr !== groupNext {
            let temp = curr?.next   // 保存下一个节点
            curr?.next = prev       // 翻转当前指针
            prev = curr             // prev 前进
            curr = temp             // curr 前进
        }
        
        // 翻转后，groupPrev.next 原先指向当前组的第一个节点，现变成组尾
        // 暂存这个节点，用于更新 groupPrev
        let tmp = groupPrev?.next
        // 将 groupPrev.next 指向翻转后的组的新头（即 kth 节点）
        groupPrev?.next = kth
        // 更新 groupPrev 为当前组翻转后的尾部，继续下一组处理
        groupPrev = tmp
    }
    
    // 返回哑节点的下一个节点，即新链表的头
    return dummy.next
}