翻转链表

文章目录

问题很简单需要将一个链表翻转，比如原来的链表是1->2->3->4->5，那么返回5->4->3->2->1。

这个问题纠结在于空间复杂度，最直白可以想到的就是用另一个链表来存一下，这样一个链表从头到尾扫一遍，另一个链表每次创建一个新的节点来指向上一个节点实现从尾到头，这样做的空间复杂度是O(n)。

那么能不能进一步，把空间复杂度降低呢？就是不需要额外的链表。

方法是有的，我们可以将原来节点A指向节点B的这个指针转一下，那么不就正好实现翻转了吗？当然因为翻转之后，节点B原来指向的空间就会泄露，比如是C->D->E没人指向C了，那么我们得用一个临时变量来存一下节点B指向的空间。这样做的空间复杂度就是O(1)。