#反转链表 #反转链表C语言

大家好，欢迎来到溜达虎的算法课。

1. 今天要讲解的题目是反转链表。首先看一下题目描述，给你一个单链表的头接点，还得请你反转链表并返回反转后的链表。

2. 通过示例一来看一下什么是反转列表。反转列表其实就是把每个节点的 next 指针指向它的前一个节点。

- 对于节点一，它没有前一个节点，所以把它指向空。

- 对于节点二，把它指向它的前一个节点。

- 对于节点三，把它指向它的前一个节点。

- 对于节点二，把它指向它的前一个节点。

- 对于节点四，把它指向它的前一个节点。

- 对于节点五，把它指向它的前一个节点。

3. 这样就得到了反转以后的列表。下面来介绍一种双指针的解法。

- 首先定义一个 pre 指针指向一个空接点，再另一个 cur 指针指向列表的第一个节点。

- 然后把 cur 指针对应的 next 指针指向 pre。

- 接下来 pre 和 cur 需要分别向右移位。重复前面的步骤，把 cur 指针对应的 next 指针指向 pre，然后 pre 和 cur 继续分别向右移位。

- 接下来把 cur 对应的 next 指针指向 pre，然后继续把 pre 和 cur 指针向右移位。这个时候 cur 指针已经指向了一个空节点，然后 pre 指针指向了原来列表的最后一个节点。只需要把 pre 指针返回就可以得到一个反转后的新列表。

4. 下面进行编码，编码的过程可以帮助大家更好地理解这个思路。

- 首先来判断一下 head 是否为空指针，如果为空，那么直接返回 head。

- 接下来定义一个 pre 指针指向空，再另一个 cur 指针指向 head。

- 当 cur 指针不为空，就把 cur 指针的 next 指针指向 pre，然后把 cur 和 pre 分别向后移一位。

- 这个时候发现 cur 的已经指向了 pre，所以在 cur 指针指向 pre 之前需要保存 cur 指向的原始节点。

- 把 temp 指针指向的节点赋给 cur，那么就相当于 cur 向后移动了一位。

- 最后返回 pre 就可以得到反转后的列表。

5. 运行一下代码，提交一下代码。

今天的视频就到这里，谢谢大家观看。