• 任务描述
• 编程要求
  • 输入
  • 输出
• 测试说明
• 来源

任务描述

本关任务：利用单链表表示一个整数序列，通过一趟遍历，将单链表中所有结点的链接方向逆转。要求空间复杂度为O(1)。

编程要求

输入

多组数据，每组数据有两行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔）。当n=0时输入结束。

输出

对于每组数据分别输出一行，逆序输出链表中的元素，元素之间用空格分隔。

测试说明

平台会对你编写的代码进行测试：

测试输入： 5 1 2 3 4 5 6 3 1 2 5 4 6 0

预期输出： 5 4 3 2 1 6 4 5 2 1 3

来源

BJFUOJ

开始你的任务吧，祝你成功

关键在于L->next，也就是头结点的指针域。它在循环的过程中，始终指向逆置的结点（也就是需要改向的，那个结点的前一个）,循环过程中p与q每次逆置向后移一位 

#include <iostream>
using namespace std;typedef struct LNode
{int data;struct LNode *next;
}LNode,*LinkList;void CreateList_R(LinkList &L,int n)
{L->next=NULL;LinkList r=new LNode;r=L;for(int i=0;i<n;i++){LinkList p=new LNode;cin>>p->data;p->next=NULL;r->next=p;r=p;}
}void Inverse(LinkList &L)
{//逆置带头结点的单链表L
/**************begin************/if(L == NULL || L->next == NULL) return; // 如果链表为空或只有一个节点，无需逆置，直接返回    a.LinkList p = L->next, q; // 初始化p指向第一个节点L->next = NULL; // 将头节点的next置为NULL   1.while(p ) {q = p->next; // 保存p的下一个节点     2.p->next = L->next; // 修改p的next指向L->next = p; // 修改头节点的next指向   3.p = q; // p移动到下一个节点 }/**************end************/
}void PrintList(LinkList &L)
{L=L->next;while(L){if(L->next!=NULL) cout<<L->data<<" ";else cout<<L->data;L=L->next;}cout<<endl;
}int main()
{int n;while(cin>>n){if(n==0) break;LinkList L=new LNode;CreateList_R(L,n);Inverse(L);PrintList(L);}return 0;
}