[面试精选] 0206. 反转链表-CSDN博客

本文链接：https://blog.csdn.net/apple_74262176/article/details/148229859

文章目录

1. 题目链接

2. 题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

3. 题目示例

示例 1 :

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2 :

输入：head = [1,2]
输出：[2,1]

4. 解题思路

问题理解：
- 给定一个单链表，要求将其反转
- 反转后原链表的头节点变为尾节点，尾节点变为头节点
- 所有节点的next指针方向需要反转
关键思路：
- 三指针法：使用pre、cur、nxt三个指针
  - pre：记录前驱节点（已反转部分的头节点）
  - cur：当前待处理节点
  - nxt：临时保存下一个待处理节点
- 指针操作：
  1. 保存当前节点的下一个节点（nxt = cur.next）
  2. 反转当前节点的指针（cur.next = pre）
  3. 前移pre指针（pre = cur）
  4. 前移cur指针（cur = nxt）
算法流程：
- 初始化pre为null，cur为head
- 遍历链表：
  - 每次处理一个节点，反转其指针方向
  - 更新pre和cur指针
- 当cur为null时，pre即为新链表的头节点

5. 题解代码

class Solution {
    public ListNode reverseList(ListNode head) {
        // pre指针用于记录前驱节点，初始为null（反转后的尾节点指向null）
        ListNode pre = null;
        // cur指针用于遍历链表，初始指向头节点
        ListNode cur = head;
        
        // 遍历链表直到当前节点为null
        while (cur != null) {
            // 临时保存当前节点的下一个节点
            ListNode nxt = cur.next;
            // 反转当前节点的指针方向，指向前驱节点
            cur.next = pre;
            // pre指针前移到当前节点
            pre = cur;
            // cur指针移动到之前保存的下一个节点
            cur = nxt;
        }
        
        // 循环结束时pre指向新的头节点
        return pre;
    }
}