题解

本题要求给定一个单链表的头节点 $head$，将链表反转，并输出反转后的链表。输入包含两行，第一行输入链表的长度 $n$，第二行输入 $n$ 个整数，代表链表中每个节点的值。输出为反转后链表中各节点的值，节点之间用空格分隔。

思路分析

反转链表的基本思路是采用迭代法。具体步骤如下：

• 初始化两个指针：$prev$ 指向空（$null$），$curr$ 指向头节点。
• 进入循环，当 $curr$ 非空时：
  • 用变量 $next\_temp$ 保存 $curr$ 的下一个节点（即 $curr.next$）。
  • 将 $curr.next$ 指向 $prev$，实现指针反转。
  • 更新 $prev$ 为当前节点 $curr$，然后更新 $curr$ 为 $next\_temp$。
• 当循环结束时，$prev$ 指向的新链表的头节点即为反转后的链表头。

算法时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，主要操作是指针的反转

C++ 解法

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct ListNode {
    int val;            // 节点的值
    ListNode* next;     // 指向下一个节点的指针
    ListNode(int x): val(x), next(nullptr) {}  // 构造函数
};

class Solution {
public:
    // 反转链表函数
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;  // 初始化前驱节点为 nullptr
        ListNode* curr = head;     // 当前节点指针指向头节点
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next; // 保存下一个节点
            curr->next = prev;               // 反转指针指向
            prev = curr;                     // 更新前驱节点
            curr = nextTemp;                 // 更新当前节点
        }
        return prev;  // 返回反转后的头节点
    }
};
int main() {
    int n;
    cin >> n;  // 输入链表长度
    if(n == 0) return 0;  // 空链表直接结束
    int x;
    cin >> x;
    ListNode* head = new ListNode(x);  // 创建头节点
    ListNode* tail = head;
    for(int i = 1; i < n; i++) {
        cin >> x;
        tail->next = new ListNode(x);  // 创建新节点并连接到链表
        tail = tail->next;
    }
    Solution sol;
    ListNode* newHead = sol.reverseList(head);  // 调用反转链表函数
    // 输出反转后的链表
    while(newHead != nullptr) {
        cout << newHead->val;
        if(newHead->next != nullptr)
            cout << " ";
        newHead = newHead->next;
    }
    return 0;
}

Python 解法

# 定义链表节点类
class ListNode:
    def __init__(self, x):
        self.val = x          # 节点的值
        self.next = None      # 下一个节点指针

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None           # 初始化前驱节点为 None
        curr = head           # 当前节点指针指向头节点
        while curr:
            next_temp = curr.next  # 保存下一个节点
            curr.next = prev       # 反转指针指向
            prev = curr            # 更新前驱节点
            curr = next_temp       # 更新当前节点
        return prev  # 返回反转后的头节点

if __name__ == "__main__":
    import sys
    # 读取输入数据
    data = sys.stdin.read().strip().split()
    if not data:
        exit(0)
    n = int(data[0])  # 链表长度
    if n == 0:
        exit(0)  # 空链表直接结束
    # 根据输入创建链表
    head = ListNode(int(data[1]))
    tail = head
    for i in range(2, n+1):
        node = ListNode(int(data[i]))
        tail.next = node
        tail = node
    sol = Solution()
    new_head = sol.reverseList(head)  # 调用反转链表函数
    # 遍历输出反转后的链表
    res = []
    while new_head:
        res.append(str(new_head.val))
        new_head = new_head.next
    print(" ".join(res))

Java 解法

import java.util.Scanner;

// 定义链表节点类
class ListNode {
    int val;           // 节点的值
    ListNode next;     // 下一个节点指针
    ListNode(int x) {
        val = x;
        next = null;
    }
}

class Solution {
    // 反转链表函数
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;  // 初始化前一个节点为 null
        ListNode curr = head;  // 当前节点指针指向头节点
        while (curr != null) {
            ListNode nextTemp = curr.next; // 保存下一个节点
            curr.next = prev;              // 反转当前节点的指针
            prev = curr;                   // 更新前一个节点
            curr = nextTemp;               // 移动到下一个节点
        }
        return prev;  // 返回反转后的头节点
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 输入链表长度
        if(n == 0) return;     // 空链表直接结束
        ListNode head = new ListNode(sc.nextInt());  // 创建头节点
        ListNode tail = head;
        for(int i = 1; i < n; i++) {
            tail.next = new ListNode(sc.nextInt());  // 创建新节点并链接到链表
            tail = tail.next;
        }
        Solution sol = new Solution();
        ListNode newHead = sol.reverseList(head);  // 调用反转链表函数
        StringBuilder sb = new StringBuilder();
        // 遍历输出反转后的链表
        while(newHead != null) {
            sb.append(newHead.val);
            if(newHead.next != null)
                sb.append(" ");
            newHead = newHead.next;
        }
        System.out.println(sb.toString());
    }
}

Leetcode 23.反转链表-原题链接

题目内容

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

输入描述

输入共两行。

• 第一行为两个个整数$n$，代表单链表的长度。

• 第二行为$n$个整数，代表单链表每个节点的值，数字之间以空格分隔。第一个整数位头节点的值。

输出描述

样例1

输入

5
1 2 3 4 5

输出

5 4 3 2 1

样例2

输入

2
1 2

输出

2 1

提示

• 链表中节点的数目范围是 $[0, 5000]$
• $-5000 <= Node.val <= 5000$