字节面试算法集第三题链表反转 #算法

大家好，我是老周。

接下来来讲字节面试题里面第三道算法题，这叫做反转链表。

这里已经告诉我们是 leetcode 的 206 的题目，反转链表。

反转链表这里其实很简单，老周这里以迭代的方式来描述了一下。

首先有一个链表是这么一个样子，1、2、3、4、5、6、7，1 是第一个节点，2 是第二个节点。每一个节点的下一个节点通过箭头来表示，而 null 就是不存在的一个点，所以 1 前面是没有节点的。

通过三个变量或者通过三个指针去指向对应的位置。首先第一个位置就是当前元素是第一个元素，当前元素的上一个元素就是没有的，第一次进去它的下一个元素就第二个元素。

要反转链表无非就是要改变箭头的方向，从这里从 1、2、3、4、5、6、7 改变箭头的方向变成这样子是不是就可以了？所以将当前元素的上一个元素变成下一个元素，下一个元素变成上一个元素就可以了。

所以就通过迭代的方式一步一步的使得指针一步一步的往后去走就行了。比如到第二步，第二步的当前节点就是变成 2 这个节点了，然后将 2 和一之间的关系给它打断，打断之后因为 1 这个节点上一个节点变成下一个节点，所以箭头方向改一下。

改完箭头方式之后由于当前节点位置变化了，所以上一个节点的指针就变成了 1 这个节点，下一个节点以此类推就变成了 3 这个节点。所以通过这种方式一步一步的迭代，然后再下一步就到这个位置了。

2 和 3 之间这个箭头打断了，变成了什么？2-1 就是上一个节点变成下一个节点，下一个节点变成了上一个节点。所以依此类推，走到最后整个链表就会被反转过来。

位置其实没有发生变化，发生变化的是什么？箭头方向发生了变化。这就是通过这种迭代的方法去对链表做反转。

这代码也给大家准备好了，非常简单。就是通过三个变量，一个叫做 pre，上一个当前的和下一个，三个变量指向不同的位置，依次迭代。

一键三连，支持老周。