当前位置：首页 > news >正文

【LeetCode 热题 100】206. 反转链表——（解法二）指针翻转

news 2025/7/8 6:44:29

Problem: 206. 反转链表
题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

【LeetCode 热题 100】206. 反转链表——（解法一）值翻转

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(1)

整体思路

这段代码旨在解决 “反转单链表” 的问题。与上一个通过修改节点值的方法不同，此版本采用的是迭代法，通过改变节点的 next 指针指向来实现真正的链表结构反转。这是解决此问题的标准、高效且最被认可的方法。

算法的核心思想是：在遍历链表的过程中，逐个地将每个节点的 next 指针“反向”，指向其前一个节点。

指针的定义与初始化：
- 算法使用了两个关键指针来追踪状态：
  - ListNode pre = null;: pre 指针用于存储当前节点 cur 的前一个节点。在反转后，cur 应该指向 pre。初始时，头节点的前一个节点是 null，所以 pre 初始化为 null。这个 null 将成为反转后新链表的尾部。
  - ListNode cur = head;: cur 指针指向当前正在处理的节点。它从头节点 head 开始。
迭代与指针反转：
- 算法使用一个 while (cur != null) 循环来遍历整个链表，直到所有节点都被处理完毕。
- 在循环的每一步，针对当前节点 cur，执行以下“四步曲”：
  a. 保存下一个节点：ListNode nxt = cur.next;
  - 这是至关重要的一步。在我们将 cur.next 的指向改变之前，必须先用一个临时指针 nxt 把 cur 原来的下一个节点保存起来。否则，一旦 cur.next 被修改，我们就会丢失通往链表其余部分的路径。
    b. 反转指针：cur.next = pre;
  - 这是核心的反转操作。将当前节点 cur 的 next 指针指向其前一个节点 pre。
    c. 更新 pre 指针：pre = cur;
  - 完成 cur 的反转后，对于下一个节点（即刚才保存的 nxt），cur 就变成了它的“前一个节点”。所以，将 pre 指针更新为 cur，为下一次迭代做准备。
    d. 更新 cur 指针：cur = nxt;
  - 将 cur 指针移动到下一个要处理的节点，即之前保存的 nxt。
返回结果：
- 当 while 循环结束时，cur 会变为 null，意味着已经处理完了所有节点。
- 此时，pre 指针恰好指向了原始链表的最后一个节点，而这个节点现在是反转后新链表的头节点。因此，返回 pre。

这个过程就像是将链表的节点逐个从旧链表上“摘下”，然后“头插”到新链表的前面，最终完成整个链表的反转。

完整代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {/*** 反转一个单链表。（迭代法）* @param head 原始链表的头节点* @return 反转后新链表的头节点*/public ListNode reverseList(ListNode head) {// pre: 指向当前节点 cur 的前一个节点。反转后，cur.next 应指向 pre。// 初始化为 null，因为原始头节点反转后将指向 null。ListNode pre = null;// cur: 指向当前正在处理的节点。ListNode cur = head;// 遍历整个链表，直到 cur 为 nullwhile (cur != null) {// 1. 临时保存当前节点的下一个节点，以防断链ListNode nxt = cur.next;// 2. 核心：反转指针，将当前节点的 next 指向前一个节点cur.next = pre;// 3. 更新 pre 指针，为下一次循环做准备。pre 向前移动到 cur 的位置。pre = cur;// 4. 更新 cur 指针，处理下一个节点。cur 向前移动到 nxt 的位置。cur = nxt;}// 循环结束后，pre 指向的就是原链表的最后一个节点，即新链表的头节点。return pre;}
}