反转链表 golang

反转链表

链表是一种常用的数据结构，在很多算法问题中都有广泛的应用。反转链表是其中一个经典的问题，我们需要编写一个函数来翻转给定链表。

问题描述

给定一个链表，我们需要反转该链表。例如，对于链表1->2->3->4->5，我们需要返回链表5->4->3->2->1。

解法思路

想要反转链表，我们需要考虑如何改变链表中节点的指向关系。具体而言，我们可以使用三个指针来完成反转过程。

1. 定义三个指针pre、cur和next，分别用来指向当前节点的前一个节点、当前节点和下一个节点。
2. 从链表的头节点开始遍历链表，每次迭代时，将当前节点的next指针指向前一个节点，完成反转。
3. 更新pre、cur和next指针，将它们分别指向当前节点、当前节点的下一个节点和下一个节点的下一个节点。
4. 重复上述步骤，直到链表的最后一个节点。
5. 将原链表的头节点指向null，返回新链表的头节点。

代码实现

下面是以Golang语言实现反转链表的代码：

``` type ListNode struct { Val int Next *ListNode } func reverseList(head *ListNode) *ListNode { var pre *ListNode cur := head for cur != nil { next := cur.Next cur.Next = pre pre = cur cur = next } return pre } ```

复杂度分析

时间复杂度：O(n)，其中n是链表的长度。需要遍历整个链表一次。

空间复杂度：O(1)，使用了常数个额外指针来完成反转过程，因此空间复杂度是常数级别的。

总结

通过使用三个指针来改变节点的指向关系，我们可以有效地反转一个链表。这个问题虽然看似简单，但实际上考察了对指针操作的理解和熟练程度。掌握了反转链表的基本思路和实现方法，对于解决其他相关问题也会有帮助。