|
链表原地翻转
链表原地翻转的意思是指针p->next是要指向它的前一个结点 因此有一个结点pre一直在p的前面 由于当前p这个结点翻转后，还需要指向下一个结点继续重复“翻转”操作，因此还需要一个指针记录p后面的结点 指针 用途 p 当前翻转 rear 指向p后面的那个结点 pre 指向p前面的那个结点
//设计一个算法，将链表所有结点的链接方向原地宣战，即要求利用原表的存储空间，换句话说，要求算法的空间复杂度为O(1)
#include
using namespace std;
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
//创建链表(后插法)
void CreateList_R(LinkList &L, int n){
L = new LNode;
L -> next = NULL;
LinkList p, r;
r = L;
for(int i = 0; i < n; i++){
p = new LNode;
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
}
}
//输出链表
void outList(LinkList L){
cout next;
pre = NULL;
L->next = NULL;
while(p){
rear = p->next;
p->next = pre;
pre = p;
p = rear;
}
L->next = pre;
return L;
}
int main(){
LinkList L, S;
CreateList_R(L, 10);
S = reverseList(L);
outList(S);
return 0;
}
|