反转链表

学习文本来源：代码随想录

力扣地址

题意：反转一个单链表
示例：

• 输入： 1->2->3->4->5->null
• 输出：5->4->3->2->1->null

思路

如果在定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。

其实只需要改变链表的next指针指向，直接将链表反转，而不用重新定义一个新的链表

之前链表的头节点是元素1，反转之后头节点就是元素5，这里并没有添加或者删除节点，仅仅是改变了next的指针方向。

首先定义一个cur，指向头结点，在定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把cur->next节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变cur->next的指向了，将cur->next指向pre，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur指针已经指向了null，循环结束，链表也反转完毕，此时我们 return pre 指针就可以了，pre指针就是指向了新的头结点。

双指针法

golang:

func reverseList(head *ListNode) *ListNode {
    now := head
    var prev *ListNode
    for now != nil {
        temp := now.Next
        now.Next = prev
        prev = now
        now = temp
    }
    return prev
}

• 时间复杂度O(n)
• 空间复杂度O(1)