我要评论记录一些链表相关的算法题的解法
更新记录：
| 日期 | 内容 |
|---|---|
| 2024/05/22 | 链表定义，反转链表，成对反转链表 |
0 准备
0.1 链表结构定义
type listnode struct {
val int
next *listnode
}
0.2 工具函数
0.2.1 生成长度为n，值随机的单链表
func generatelist(n int) *listnode {
var head *listnode
for i := 0; i < n; i++ {
node := &listnode{val: rand.intn(100)}
if head == nil {
head = node
} else {
node.next = head
head = node
}
}
return head
}
0.2.2 遍历输出链表
func printlist(head *listnode) {
for head != nil {
print(head.val, " ")
head = head.next
}
println()
}
1 反转单链表
1.1 问题描述
给定一个单链表的头结点phead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围：
0≤n≤1000
要求：空间复杂度 o(1) ，
时间复杂度 o(n) 。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
1.2 迭代方式
1.2.1 思路描述
- 需要声明两个指针类型变量，
cur指向当前链表节点（初始为head），prev存放该链表节点的前置节点 - 迭代方式求解问题就像剥洋葱，一层一层地解决问题，问题的规模会随着迭代的深入变得越来越小，当满足某种终止条件时，最后的问题得到解决，也就意味着解决了全部问题
- 针对此问题，由于
cur初始时指向链表头结点，因此迭代解决该问题其实就是从头结点开始，将cur的前置节点变为后置节点，同时将后置节点变为前置节点，然后对cur进行迭代（执行下一个节点），直至cur为空值（意味着链表走到了尽头）
1.2.2 代码
// 迭代方式反转链表
func reverselistiter( head *listnode ) *listnode {
cur := head // 需要迭代的主体
var prev *listnode // 迭代过程中需要记录的上一个节点
for cur!= nil {
// 迭代过程中，记录当前节点的下一个节点，避免丢失
tmp := cur.next
// 迭代过程中，将当前节点的下一个节点指向上一个节点
cur.next = prev
// 迭代过程中，将上一个节点指向当前节点
prev = cur
// 迭代过程中，将当前节点指向下一个节点
cur = tmp
}
// 迭代完成后，将头节点指向最后一个节点
head = prev
return head
}
1.2.3 验证
func main() {
head := generatelist(10)
printlist(head)
printlist(reverselistiter(head))
}
运行结果：
1.3 递归方式
1.3.1 思路描述
- 递归的基本情况是：长度为0或1的链表，反转的结果是其本身
- 否则，对于长度为n的链表，反转该链表相当于将该链表的头结点拼接到第2个节点到第n个节点组成的长度为n-1的链表反转后的链表尾结点之后
- 递归进行第2步直到达到基本情况
1.3.2 代码
func reverselistrecur(head *listnode) *listnode {
// 递归终止条件
if head == nil || head.next == nil {
return head
}
// 递归反转剩余部分
newhead := reverselistrecur(head.next)
// 反转当前节点
head.next.next = head
head.next = nil
return newhead
}
1.3.3 验证
func main() {
head := generatelist(10)
printlist(head)
printlist(reverselistrecur(head))
}
运行结果：
2 成对反转链表
2.1 描述
一对一对的反转链表内的结点
for example,
given1->2->3->4, return 2->1->4->3.
2.2 迭代方式
2.2.1 思路
- 使用一个虚拟头节点 dummy，指向链表的头节点。这有助于处理边界情况。
- 使用三个指针：prev（指向每对节点的前一个节点，初始指向 dummy），first（指向每对节点中的第一个节点），second（指向每对节点中的第二个节点）。
- 逐步交换每对节点，并更新指针以处理下一对节点。
2.2.2 代码
func reverselistpairiter(head *listnode) *listnode {
dummy := &listnode{next: head}
prev := dummy
for head != nil && head.next != nil {
first := head
second := head.next
// 交换节点
first.next = second.next
second.next = first
prev.next = second
// 迭代
prev = first
head = first.next
}
return dummy.next
}
2.2.3 验证
func main() {
head := generatelist(11)
printlist(head)
printlist(reverselistpairiter(head))
}
运行结果：
2.3 递归方式
2.3.1 思路
- 基本情况：如果链表为空或只有一个节点，不需要交换，直接返回头节点。
- 递归处理剩余链表的交换操作。
- 交换当前两节点，然后将递归处理的结果连接到交换后的节点后面。
2.3.2 代码
func reverselistpairrecur(head *listnode) *listnode {
// 基本情况
if head == nil || head.next == nil {
return head
}
tmp := head.next
head.next = reverselistpairrecur(tmp.next)
tmp.next = head
return tmp
}
2.3.3 验证
func main() {
head := generatelist(11)
printlist(head)
printlist(reverselistpairrecur(head))
}
运行结果：
发表评论