Go中的指针指向指针(双指针)
Go编程语言中的指针是一个变量,用于存储另一个变量的内存地址。指针是一个特殊的变量,因此它甚至可以指向任何类型的变量。基本上,这看起来像是一个指针链。当我们定义一个指向指针的指针时,第一个指针将用于存储第二个指针的地址。这个概念有时被称为双指针。
双指针是一种常用的算法技巧,它通过使用两个指针来遍历数据结构,从而在一次遍历中解决问题,避免使用额外的数据结构,从而降低时间复杂度和空间复杂度。双指针技巧通常用于解决链表和数组相关的问题,下面我们将详细介绍双指针的应用场景和举例用法。
1.双指针的类型
快慢指针
快慢指针一般用于解决链表相关的问题。快指针每次移动两步,慢指针每次移动一步。通过快慢指针的遍历,可以找到链表的中间节点、判断链表是否有环、寻找链表倒数第k个节点等问题。
例如,判断链表中是否含有环的问题,可以使用快慢指针的方法。快指针每次移动两步,慢指针每次移动一步,如果链表中有环,快指针最终会追上慢指针。
左右指针
左右指针一般用于解决数组或字符串相关的问题。左指针从数组的最左边开始,右指针从数组的最右边开始,然后向中间移动。通过左右指针的遍历,可以找到满足某种条件的子数组或子字符串,比如两数之和、反转数组、滑动窗口等问题。
使用示例
在下面的程序中,指针pt2存储pt1指针的地址。解引用pt2即* pt2将给出变量v的地址,或者您也可以说指针pt1的值。如果您尝试** pt2,那么将给出变量v的值,即100。
package main
import "fmt"
func main() {
//整数类型变量
var V int = 100
//获取一个指针
//的整数类型
var pt1 *int = &V
//获取指向的指针
//指向pt1的指针存储地址
//将pt1转化为pt2
var pt2 **int = &pt1
fmt.Println("变量V的值为 = ", V)
fmt.Println("变量V的地址为 = ", &V)
fmt.Println("pt1的值为 = ", pt1)
fmt.Println("pt1地址为 = ", &pt1)
fmt.Println("pt2的值为 = ", pt2)
//解引用
//指向指针的指针
fmt.Println("pt2地址的值为(*pt2) = ", *pt2)
//双指针将给出变量V的值
fmt.Println("*(pt2地址处的值为) 或 **pt2 = ", **pt2)
}
输出:
变量V的值为 = 100 变量V的地址为 = 0xc000062090 pt1的值为 = 0xc000062090 pt1地址为 = 0xc00008c018 pt2的值为 = 0xc00008c018 pt2地址的值为(*pt2) = 0xc000062090 *(pt2地址处的值为) 或 **pt2 = 100
2.使用方法
在Go语言中,双指针通常指的是指向指针的指针,也就是二级指针。这在C语言中比较常见,但在Go语言中使用得较少,因为Go的指针使用已经非常灵活,而且Go鼓励使用切片(slice),它在内部处理了动态数组的复杂性。
不过,如果你确实需要使用双指针,比如在某些底层操作或者特定的算法实现中,可以这样声明和使用双指针:
package main
import "fmt"
func main() {
// 定义一个变量
var value int = 100
// 定义一个指针,指向value
var ptr *int = &value
// 定义一个双指针,指向ptr
var ptrToPtr **int = &ptr
// 输出原始变量的值
fmt.Println("Value:", value)
// 输出ptr指向的值
fmt.Println("Value pointed by ptr:", *ptr)
// 输出ptrToPtr指向的ptr的值
fmt.Println("Value pointed by ptrToPtr:", **ptrToPtr)
// 通过双指针修改原始变量的值
**ptrToPtr = 200
// 输出修改后的原始变量的值
fmt.Println("Value after modification through ptrToPtr:", value)
}
在这个例子中,ptr
是一个一级指针,它存储了变量 value
的内存地址。ptrToPtr
是一个二级指针,它存储了 ptr
的内存地址。通过解引用操作符 *
,我们可以访问指针指向的值。在Go中,解引用操作符 *
用于获取指针指向的值,而 &
用于获取变量的内存地址。
注意:Go语言中通常不需要使用双指针,除非你在编写底层代码或者进行某些特定的算法实现。在大多数情况下,使用切片和映射(map)会更加安全和方便。
3.双指针的应用实例
移除元素
左右指针+交换值 在这个问题中,可以使用左右指针的方法来移除数组中的特定元素。左指针从数组的开始遍历,右指针从数组的末尾遍历,通过交换元素来移除不需要的值。
package main
import "fmt"
func removeElement(nums []int, val int) int {
// 使用左指针i来遍历数组
i := 0
// 使用右指针j来指向将要放置的元素
for j := 0; j < len(nums); j++ {
if nums[j] != val {
nums[i] = nums[j]
i++
}
}
return i
}
func main() {
nums := []int{3, 2, 2, 3}
val := 3
newLength := removeElement(nums, val)
fmt.Println("Array after removing elements:", nums[:newLength])
}
两数之和
在这个问题中,可以使用左右指针来找到两个数,使得它们的和等于目标值。由于数组是有序的,我们可以通过移动左右指针来调整和的大小,直到找到满足条件的两个数。
package main
import "fmt"
func twoSum(nums []int, target int) []int {
left, right := 0, len(nums)-1
for left < right {
sum := nums[left] + nums[right]
if sum == target {
return []int{left + 1, right + 1}
} else if sum < target {
left++
} else {
right--
}
}
return []int{-1, -1}
}
func main() {
nums := []int{2, 7, 11, 15}
target := 9
result := twoSum(nums, target)
fmt.Println("Indexes of the two numbers:", result)
}
反转数组
在这个问题中,可以使用左右指针来反转数组。左指针从数组的开始遍历,右指针从数组的末尾遍历,通过交换左右指针指向的元素来实现数组的反转。
package main
import "fmt"
func reverseArray(nums []int) {
left, right := 0, len(nums)-1
for left < right {
// 交换左右指针指向的元素
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
func main() {
nums := []int{1, 2, 3, 4}
reverseArray(nums)
fmt.Println("Reversed array:", nums)
}
这些示例展示了如何使用双指针技巧来解决实际问题。在实际应用中,你可能需要根据具体问题调整这些代码。例如,对于链表问题,你需要使用链表节点的指针,而对于数组问题,你可以直接使用索引。这些示例提供了一个基本的框架,你可以根据需要进行修改和扩展。
4.双指针的使用场景
- 链表问题:如判断链表是否有环、找到链表的中间节点、寻找链表的倒数第k个节点等。
- 数组问题:如两数之和、反转数组、滑动窗口等。
- 动态内存管理:在需要动态分配和释放内存的场景下,可以使用二级指针来管理内存。
- 函数参数传递:在需要在函数内部修改指针变量的指向时,可以通过传递二级指针来实现。
- 多维数组操作:在处理多维数组时,二级指针可以简化内存管理和数据访问。