反转链表

字数 2494 2025-11-02 00:26:30

反转链表

题目描述
反转链表是一道非常经典的面试题。题目要求将一个单链表的所有节点顺序反转，并返回反转后链表的头节点。例如，给定链表 1 -> 2 -> 3 -> 4 -> 5，反转后应变为 5 -> 4 -> 3 -> 2 -> 1。这道题考察对链表数据结构的理解和指针（引用）操作的熟练度。

解题过程

我们将使用迭代的方法来解决这个问题，这是最直观和高效的方法之一。整个过程可以理解为一边遍历链表，一边将每个节点的指向“掰”向相反的方向。

核心思路
我们需要三个指针来协同工作：

prev：指向当前节点的前一个节点（初始为 null，因为反转后原链表的头节点将变成尾节点，其 next 应指向 null）。
curr：指向当前正在处理的节点。
next：临时保存当前节点的下一个节点，防止在修改 curr.next 的指向后，链表断裂，导致丢失后续的节点。

步骤分解

假设我们有一个链表：1 -> 2 -> 3 -> 4 -> 5 -> null。我们的目标是将它反转为 5 -> 4 -> 3 -> 2 -> 1 -> null。

步骤零：初始化
- 在开始遍历之前，我们设置 prev 指针为 null，curr 指针指向链表的头节点（即节点 1）。
- 此时状态：prev = null, curr = 1。
- 链表：1 -> 2 -> 3 -> 4 -> 5 -> null
步骤一：处理第一个节点（节点 1）
1. 保存下一个节点：首先，我们需要一个临时指针 next 来保存 curr 的下一个节点，即节点 2。next = curr.next （next = 2）。这一步至关重要，因为下一步我们将修改 curr.next，如果不提前保存，就会丢失节点 2 的引用。
2. 反转指针：然后，我们将当前节点 curr (节点 1) 的 next 指针指向它的前一个节点 prev（此时是 null）。执行 curr.next = prev。现在，节点 1 指向了 null。链表变成了 1 -> null，而 2 -> 3 -> 4 -> 5 这部分由 next 指针保存着。
3. 指针前移：现在，我们已经完成了节点 1 的反转。接下来要处理节点 2。我们将 prev 指针移动到 curr 的位置（即节点 1），将 curr 指针移动到 next 的位置（即节点 2）。执行 prev = curr （prev = 1），然后 curr = next （curr = 2）。
- 此时状态：prev = 1, curr = 2, next = 2。
- 当前反转部分：1 -> null
- 剩余链表：2 -> 3 -> 4 -> 5 -> null
步骤二：处理第二个节点（节点 2）
1. 保存下一个节点：next = curr.next （next = 3）。
2. 反转指针：curr.next = prev。让节点 2 的 next 指向节点 1。现在链表结构是 2 -> 1 -> null。
3. 指针前移：prev = curr （prev = 2），curr = next （curr = 3）。
- 此时状态：prev = 2, curr = 3, next = 3。
- 当前反转部分：2 -> 1 -> null
- 剩余链表：3 -> 4 -> 5 -> null
步骤三：处理第三个节点（节点 3）
1. 保存下一个节点：next = curr.next （next = 4）。
2. 反转指针：curr.next = prev。让节点 3 的 next 指向节点 2。现在链表结构是 3 -> 2 -> 1 -> null。
3. 指针前移：prev = curr （prev = 3），curr = next （curr = 4）。
- 此时状态：prev = 3, curr = 4, next = 4。
- 当前反转部分：3 -> 2 -> 1 -> null
- 剩余链表：4 -> 5 -> null
步骤四和五：以此类推...
- 我们会重复这个过程，直到处理完最后一个节点（节点 5）。
步骤六：处理最后一个节点（节点 5）及终止条件
1. 此时 curr 指向节点 5，prev 指向节点 4。链表状态是 4 -> 3 -> 2 -> 1 -> null，剩余 5 -> null。
2. 保存下一个节点：next = curr.next （next = null）。
3. 反转指针：curr.next = prev。让节点 5 的 next 指向节点 4。链表结构变为 5 -> 4 -> 3 -> 2 -> 1 -> null。
4. 指针前移：prev = curr （prev = 5），curr = next （curr = null）。
- 现在，curr 指针为 null，这意味着我们已经遍历完了原始链表的所有节点。
返回结果
- 循环结束后，prev 指针指向的就是反转后新链表的头节点，也就是原始链表的尾节点（节点 5）。因此，我们最终返回 prev。

总结
这个迭代算法的核心在于每一步都执行相同的四个操作：

临时保存当前节点的下一个节点（next = curr.next）。
将当前节点的指针指向前一个节点（反转操作，curr.next = prev）。
前移 prev 指针（prev = curr）。
前移 curr 指针（curr = next）。

循环的终止条件是 curr 指针变为 null。整个算法的时间复杂度是 O(n)，n 为链表长度，因为我们只遍历了一次链表。空间复杂度是 O(1)，因为我们只使用了固定的几个指针，没有使用额外的数据结构。

反转链表题目描述反转链表是一道非常经典的面试题。题目要求将一个单链表的所有节点顺序反转，并返回反转后链表的头节点。例如，给定链表 1 -> 2 -> 3 -> 4 -> 5，反转后应变为 5 -> 4 -> 3 -> 2 -> 1。这道题考察对链表数据结构的理解和指针（引用）操作的熟练度。解题过程我们将使用迭代的方法来解决这个问题，这是最直观和高效的方法之一。整个过程可以理解为一边遍历链表，一边将每个节点的指向“掰”向相反的方向。核心思路我们需要三个指针来协同工作： prev ：指向当前节点的前一个节点（初始为 null，因为反转后原链表的头节点将变成尾节点，其 next 应指向 null）。 curr ：指向当前正在处理的节点。 next ：临时保存当前节点的下一个节点，防止在修改 curr.next 的指向后，链表断裂，导致丢失后续的节点。步骤分解假设我们有一个链表：1 -> 2 -> 3 -> 4 -> 5 -> null。我们的目标是将它反转为 5 -> 4 -> 3 -> 2 -> 1 -> null。步骤零：初始化在开始遍历之前，我们设置 prev 指针为 null ， curr 指针指向链表的头节点（即节点 1）。此时状态： prev = null , curr = 1 。链表： 1 -> 2 -> 3 -> 4 -> 5 -> null 步骤一：处理第一个节点（节点 1）保存下一个节点：首先，我们需要一个临时指针 next 来保存 curr 的下一个节点，即节点 2。 next = curr.next （ next = 2 ）。这一步至关重要，因为下一步我们将修改 curr.next ，如果不提前保存，就会丢失节点 2 的引用。反转指针：然后，我们将当前节点 curr (节点 1) 的 next 指针指向它的前一个节点 prev （此时是 null ）。执行 curr.next = prev 。现在，节点 1 指向了 null 。链表变成了 1 -> null ，而 2 -> 3 -> 4 -> 5 这部分由 next 指针保存着。指针前移：现在，我们已经完成了节点 1 的反转。接下来要处理节点 2。我们将 prev 指针移动到 curr 的位置（即节点 1），将 curr 指针移动到 next 的位置（即节点 2）。执行 prev = curr （ prev = 1 ），然后 curr = next （ curr = 2 ）。此时状态： prev = 1 , curr = 2 , next = 2 。当前反转部分： 1 -> null 剩余链表： 2 -> 3 -> 4 -> 5 -> null 步骤二：处理第二个节点（节点 2）保存下一个节点： next = curr.next （ next = 3 ）。反转指针： curr.next = prev 。让节点 2 的 next 指向节点 1。现在链表结构是 2 -> 1 -> null 。指针前移： prev = curr （ prev = 2 ）， curr = next （ curr = 3 ）。此时状态： prev = 2 , curr = 3 , next = 3 。当前反转部分： 2 -> 1 -> null 剩余链表： 3 -> 4 -> 5 -> null 步骤三：处理第三个节点（节点 3）保存下一个节点： next = curr.next （ next = 4 ）。反转指针： curr.next = prev 。让节点 3 的 next 指向节点 2。现在链表结构是 3 -> 2 -> 1 -> null 。指针前移： prev = curr （ prev = 3 ）， curr = next （ curr = 4 ）。此时状态： prev = 3 , curr = 4 , next = 4 。当前反转部分： 3 -> 2 -> 1 -> null 剩余链表： 4 -> 5 -> null 步骤四和五：以此类推... 我们会重复这个过程，直到处理完最后一个节点（节点 5）。步骤六：处理最后一个节点（节点 5）及终止条件此时 curr 指向节点 5， prev 指向节点 4。链表状态是 4 -> 3 -> 2 -> 1 -> null ，剩余 5 -> null 。保存下一个节点： next = curr.next （ next = null ）。反转指针： curr.next = prev 。让节点 5 的 next 指向节点 4。链表结构变为 5 -> 4 -> 3 -> 2 -> 1 -> null 。指针前移： prev = curr （ prev = 5 ）， curr = next （ curr = null ）。现在， curr 指针为 null ，这意味着我们已经遍历完了原始链表的所有节点。返回结果循环结束后， prev 指针指向的就是反转后新链表的头节点，也就是原始链表的尾节点（节点 5）。因此，我们最终返回 prev 。总结这个迭代算法的核心在于每一步都执行相同的四个操作：临时保存当前节点的下一个节点（ next = curr.next ）。将当前节点的指针指向前一个节点（反转操作， curr.next = prev ）。前移 prev 指针（ prev = curr ）。前移 curr 指针（ curr = next ）。循环的终止条件是 curr 指针变为 null 。整个算法的时间复杂度是 O(n)，n 为链表长度，因为我们只遍历了一次链表。空间复杂度是 O(1)，因为我们只使用了固定的几个指针，没有使用额外的数据结构。