力扣 206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
方案一：通过过滤器将所有非零元素顺序前置。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
// 定义一个指针用来承载结果
var pre *ListNode
// 遍历链表
for head != nil {
// 预先记录下一个节点的信息
next := head.Next
// 反转节点
head.Next = pre
// 更新保存结果的指针信息
pre = head
// 更新当前遍历的节点位置
head = next
}
return pre
}
- 时间复杂度：O(n)，因为需要遍历链表中所有元素才能实现反转，所以时间复杂度为 O(n)。
- 空间复杂度：O(1)，因为使用了常数量个变量用作辅助计算，所以空间复杂度为 O(1)。