反转链表的C程序

1. 反转链表问题

在计算机科学中，经常需要处理链表这种数据结构，而其中比较重要的操作是反转链表。反转链表意味着将原来的链式结构倒序排列，如下图所示：



反转链表的思路分为两部分，首先需要遍历整个链表，将链表节点的指针方向全部修改，这样链表节点的顺序就被逆转了。其次，需要记录反转后链表的头节点和尾节点。

2. 问题描述

现给出一个单向链表，需要编写一个程序将其逆序排列。

3. 设计思路

3.1 遍历链表，反转指针

实现链表反转的第一步是遍历链表，同时需要记录当前节点、上一节点和下一节点指针。具体实现如下：

// 定义节点结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
    ListNode *prev = NULL, *cur = head, *next;
    while (cur) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

反转链表的过程是从头开始，将当前节点的下一个节点反向指向前一个节点，这里需要使用到中间变量prev和next。

3.2 返回新的头部指针

在链表反转的过程中，需要新的头节点和尾节点分别记录新链表的起始和终止位置。具体实现如下：

ListNode* reverseList(ListNode* head) {
    ListNode *prev = NULL, *cur = head, *next;
    while (cur) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

在遍历链表时，当当前节点为尾节点时，链表反转完成。这时，prev指向的就是新链表的头节点，需要将其返回给调用者。

4. 时间复杂度分析

由于遍历链表需要访问链表的每个节点，因此时间复杂度为O(n)，其中n为链表节点个数。虽然需要使用几个指针记录待反转节点的位置，但空间复杂度仍为O(1)。

5. 程序演示

下面是本题的完整程序代码：

#include <iostream>
// 单链表结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
// 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode *prev = NULL, *cur = head, *next;
    while (cur) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}
// 打印链表
void printList(ListNode *head) {
    ListNode *cur = head;
    while(cur) {
        std::cout << cur->val << " ";
        cur = cur->next;
    }
}
int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    std::cout << "Original List:" << std::endl;
    printList(head);
    ListNode *newHead = reverseList(head);
    std::cout << "\nNew List:" << std::endl;
    printList(newHead);
    return 0;
}

该程序将原链表反转，并输出反转后的链表节点值，同时检查头节点和尾节点是否正确。程序输出结果如下：

Original List:
1 2 3 4 5
New List:
5 4 3 2 1

6. 总结

反转链表是一个基础的数据结构问题，常常出现在各种面试题中。对于学习者来说，深入理解反转链表的实现过程对于自己的编程技能水平提高是十分有帮助的。本文通过介绍反转链表的思路和实现过程，在保持简洁易懂的同时，让读者了解到链表相关的一些基本知识点，并能够在实际编程中灵活应用。