双指针法同向扫描的经典应用
- 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数。
示例：
输入：nums = [2, 7, 11, 15], target = 9 输出：[0, 1] 解释：nums[0] + nums[1] = 2 + 7 = 9，因此返回 [0, 1]。
解题思路：
用哈希表存储数组中的元素及其下标，然后遍历数组，对于每个元素，在哈希表中查找是否存在与 target 减去该元素的差值相等的元素，如果存在，返回两个元素的下标即可。
时间复杂度：O(n) 空间复杂度：O(n)
- 反转字符串
给定一个字符数组，将其反转。
示例：
输入：["h", "e", "l", "l", "o"] 输出：["o", "l", "l", "e", "h"]
解题思路：
双指针法，定义左指针 left 和右指针 right，分别指向数组的头和尾。然后交换 left 和 right 指向的元素，直到 left 大于等于 right。
时间复杂度：O(n) 空间复杂度：O(1)
- 链表的反转
给定一个链表，反转链表后，返回新链表的头节点。
示例：
输入：1->2->3->4->5->NULL 输出：5->4->3->2->1->NULL
解题思路：
双指针法，定义一个指针 cur 指向当前节点，一个指针 pre 指向前一个节点，另一个指针 next 指向当前节点的下一个节点。然后依次将当前节点指向前一个节点，然后依次将 pre、cur、next 向右移动一个节点，直到 cur 指向链表的尾节点。
时间复杂度：O(n) 空间复杂度：O(1)
- 删除链表的倒数第 N 个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。
示例：
输入：1->2->3->4->5，n = 2 输出：1->2->3->5
解题思路：
双指针法，定义一个指针 fast 先向右移动 n 个节点，然后再定义一个指针 slow，两个指针同时向右移动，直到 fast 指向链表的尾节点。此时 slow 指向的节点就是要删除的节点的前一个节点，将其指向下下个节点即可。
时间复杂度：O(n) 空间复杂度：O(1)
- 判断链表是否有环
给定一个链表，判断链表中是否有环。
示例：
输入：1->2->3->4->5->2 输出：true
解题思路：
双指针法，定义一个指针 slow 和一个指针 fast，slow 每次向右移动一个节点，fast 每次向右移动两个节点，如果链表中有环，那么 slow 和 fast 最终一定会相遇，否则 fast 会先到达链表的尾节点。
时间复杂度：O(n) 空间复杂度：O(1
原文地址: https://www.cveoy.top/t/topic/c4sW 著作权归作者所有。请勿转载和采集!