PTA（链表）2-8 单链表逆置

2-8 单链表逆置

分数 3

作者 段华琼

单位 成都锦城学院

将单链表倒置，要求只利用原表的存储空间。

原单链表如下所示：

倒置后的单链表应为：

输入格式:

第一行输入n的值，表示单链表的元素个数。
第二行输入n个整数值，作为单链表的各元素值。

输出格式:

输出倒置后的单链表的各元素值，各元素值之间用空格分隔。

输入样例1:

4
2 4 6 8

输出样例1:

8 6 4 2

输入样例2:

7
1 3 5 7 9 11 13

输出样例2:

13 11 9 7 5 3 1

4
2 4 6 8
8 6 4 2 

第二次碰到这个单链表的逆置，但是是第一次自己手敲出来，第一次完全不知道咋做，用到了三指针法：PTA（链表）1-2 单链表逆转 | zhangzhang-blog

答案

#include<iostream>
using namespace std;

// 定义链表结构
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化链表
void initList(LinkList &L) {
    L = new LNode;
    L->next = NULL;
}

// 尾插法插入链表
void insertAtTail(LinkList &tail, int num) {
    LinkList newNode = new LNode;
    newNode->data = num;
    newNode->next = NULL;
    tail->next = newNode;
    tail = newNode; // 更新尾指针
}

// 将链表反转
void reverseList(LinkList &L) {
    LinkList prev = NULL; // 让第一个处理的结点指向NULL
    LinkList curr = L->next;
    LinkList next = NULL;
    while (curr != NULL) {
        next = curr->next; // 先保存下一个结点，因为马上此节点和下一个结点之间会断开
        curr->next = prev; // 此节点反转，指向之前的那个结点
        prev = curr; // 移动prev，方便下次下一个结点指向此节点
        curr = next;
    }
    // 此时L还指向头结点，让头节点指向prev，prev现在是指向第一个结点的指针
    L->next = prev;
}

// 打印链表
void printList(LinkList L) {
    LinkList p = L->next; // 便于遍历链表
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
}

int main() {
    LinkList L;
    initList(L);

    // 将读取的数据插入到链表
    int n;
    cin >> n;
    int num;
    LinkList tail = L; // 定义尾指针，便于按读取顺序存储
    for (int i = 0; i < n; ++i) {
        cin >> num;
        insertAtTail(tail, num);
    }

    // 反转链表
    reverseList(L);
    // 打印链表
    printList(L);
}