206.反转链表
一、问题描述
反转一个单链表。
示例:
plaintext
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL二、方案一：迭代法
1、思路
使用迭代法反转链表。迭代法通常涉及三个指针：当前指针 cur、前一个指针 prev 和下一个指针 next。初始时，prev 和 next 都设置为 nil。然后，我们遍历链表，每次迭代中，将 cur 的下一个节点保存下来，赋值为 next，将 cur 的前一个节点设置为 prev，最后将 cur 移动到 next。
2、代码实现
go
func reverseList(head *ListNode) *ListNode {
var cur = head
var prev, next *ListNode
for cur != nil {
next = cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}3、复杂度分析
- 时间复杂度：O(n)，其中 n 是链表的长度。我们需要遍历整个链表一次。
- 空间复杂度：O(1)，不需要额外的空间。
三、方案二：递归法
1、思路
使用递归法反转链表。递归法的基本思路是：
- 设置当前节点的下一个节点的指针指向前一个节点。
- 递归地反转剩余的链表。
2、代码实现
go
func reverseList(head *ListNode) *ListNode {
// 定义一个辅助函数 reverse，它接受两个参数：
// prev：前一个节点
// cur：当前节点
return reverse(nil, head)
}
func reverse(prev *ListNode, cur *ListNode) *ListNode {
// 如果当前节点 cur 为 nil，则递归结束，返回前一个节点 prev
if cur == nil {
return prev
}
// 保存当前节点的下一个节点
next := cur.Next
// 将当前节点的下一个节点设置为前一个节点，实现反转
cur.Next = prev
// 递归调用 reverse 函数，将 next 作为新的当前节点，prev 作为新的前一个节点
return reverse(cur, next)
}3、复杂度分析
- 时间复杂度：O(n)，其中 n 是链表的长度。我们需要遍历整个链表一次。
- 空间复杂度：O(n)，递归调用栈的空间。
四、总结
| 方案 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 迭代法 | O(n) | O(1) |
| 递归法 | O(n) | O(n) |
迭代法在空间复杂度上更优，而递归法在代码结构上更简洁。选择哪种方法取决于具体的使用场景和个人偏好。