⭐ 题目日期：

美团 - 2024/12/3

🌳 题目描述：

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

示例 1：
输入：head = [1, 3, 5, 7]
输出：[7, 5, 3, 1]

解释图例：

🕵🏽‍♂️ 面试评估：

这道题主要考察候选者是否能认识到需要通过指针操作来反转链表的结构，正确应用迭代或递归的方法进行指针调整，并合理地处理链表的遍历以及反转逻辑。

🧗难度系数：

⭐️

📝思路分析：

这道题我们采用迭代法

1. 使用三个指针来遍历，其中：

   • pre 指向当前节点的前一个节点，初始为 null，因为反转后链表的尾节点（新链表的头节点）会指向 null。
   • cur 指向当前遍历的节点，初始值为 head。
   • nextNode 用于保存当前节点的下一个节点，防止链表反转之后与后面的元素断开。

2. 遍历链表，将当前节点的 next 指针指向 pre。

3. 向前移动三个指针：pre 指向 cur，cur 指向 nextNode。

4. 遍历结束时，pre 就是反转后的链表头节点。

以案例为例，详细图解如下所示：

💻代码(Java、Python、C++)：

Java

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode nextNode = cur.next; // 保存下一个节点
            cur.next = pre;               // 反转当前节点的指针
            pre = cur;                    // 移动 pre 指针
            cur = nextNode;               // 移动 cur 指针
        }

        return pre;
    }
}

Python

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head

        while cur:
            next_node = cur.next  # 保存下一个节点
            cur.next = pre        # 反转当前节点的指针
            pre = cur             # 移动 pre 指针
            cur = next_node       # 移动 cur 指针

        return pre

C++

#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;

        while (cur != nullptr) {   
            ListNode* next_node = cur->next; // 保存下一个节点
            cur->next = pre;                  // 反转当前节点的指针
            pre = cur;                        // 移动 pre 指针
            cur = next_node;                  // 移动 cur 指针
        }
        
        return pre; 
    }
};

🚵🏻复杂度分析：

• 时间复杂度：O(n)，其中 n 为链表中节点的数量。需要遍历所有节点一次。
• 空间复杂度：O(1)，只使用了常数空间来存储指针。

🔬在线评测(Online Judge):

题目链接