6-4 翻转链表（C++版） 分数 25 作者 李廷元 单位 中国民用航空飞行学院 本题要求实现翻转一个链表的功能。链表类ListNode的定义已经给出。要求在Solution类中给出有关函数的实现。 函数接口定义： /* * 翻转链表。head为链表的头指针。 * 函数返回值为翻转后的链表的头指针。 */ ListNode *reverse(ListNode *head); /* * 数组arr存储创建链表用的数据，n为数组长度。 * 函数返回值为创建的新链表的头指针。 */ L

下面是 ListNode 类的定义和 reverse 函数的实现：

#include <iostream>
using namespace std;

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverse(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode *prev = NULL;
        ListNode *cur = head;
        ListNode *next = head->next;
        while (next != NULL) {
            cur->next = prev;
            prev = cur;
            cur = next;
            next = next->next;
        }
        cur->next = prev;
        return cur;
    }
};

ListNode* createList(int arr[], int n) {
    if (n == 0) {
        return NULL;
    }
    ListNode *head = new ListNode(arr[0]);
    ListNode *tail = head;
    for (int i = 1; i < n; i++) {
        ListNode *node = new ListNode(arr[i]);
        tail->next = node;
        tail = node;
    }
    return head;
}

void printList(ListNode *head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(int);
    ListNode *head = createList(arr, n);
    printList(head);
    Solution sol;
    ListNode *newHead = sol.reverse(head);
    printList(newHead);
    return 0;
}

在 reverse 函数中，我们设置了三个指针 prev、cur 和 next，分别表示当前节点的前一个节点、当前节点和当前节点的后一个节点。我们从头节点开始遍历链表，每次将当前节点的 next 指针指向 prev，然后将 prev、cur、next 分别向后移动一个节点。需要注意的是，当 next 指针为 NULL 时，cur 指向的节点就是原链表的尾节点，需要将它的 next 指针指向 prev，然后返回 cur。

在测试程序中，我们先通过 createList 函数创建一个链表，然后调用 printList 函数打印出来。接着创建 Solution 类的对象 sol，调用它的 reverse 函数翻转链表。最后再次调用 printList 函数打印翻转后的链表。