单链表就地逆置有几种方法

什么叫单链表就地逆置？~

1、单链表就地逆置是一种算法。
2、如果是顺序存储的话，我们很容易想到解题思路，利用1个辅助变量让第1个元素与第n个元素交换，然后再利用这个辅助变量让第2个元素与第n-1个元素交换，...最后利用这个辅助变量让第n/2个元素与第n+1-n/2个元素交换。
3、如果不要求“就地”的话，可以创建一个n个元素辅助数组，一次访问单链表中的每个元素，并存储到该数组中，然后再依次访问单链表中的每一个元素，同时从该数组的末尾开始为单链表中的元素赋值，直到数组第1个元素的值赋值给单链表最后一个元素。
4、如果单链表为空或单链表中只有头结点，那么单链表不需要逆置，如果单链表中只有一个元素，逆置之后它的位置还是不会改变，所以可以不逆置。当单链表中有2个或两个以上的元素时，从第1个元素断开，令它的next为空，依次访问第2个元素到第n个元素，当访问到其中的任意一个元素时，将它插入到头结点之后，也就是把它插入到第1个位置，这样原始的第1个元素就会被后面的n-1个元素插入到它的前面，原始的第2个元素就会被后面的n-2个元素插入到它的前面，...直到原始的第n个元素插入到第1个位置。这样就实现了带头结点的单链表的就地逆置。

比如说链表
a -> b -> c -> d
表头是a，表尾是d。就地逆置的意思就是变成：
a <- b <- c <- d
a变成表尾，d变成表头

假设
struct LINK {
int value;
struct LINK * next;
};
struct LINK a, b, c, d;
a->next = &b;
b->next = &c;
c->next = &d;
d->next = 0;
逆置后：
b->next = &a;
c->next = &b;
d->next = &c;
a->next = 0;

所谓就地逆置，就是在操作中，遇到a->next = &b;的情况，那么改写为b->next = &a;

单链表就地逆置的两种(递归与普通循环)
1.用递归算法,对于不带头结点的单链表（a1,a2,a3,a4,a5,a6）逆置后的结果为（a6,a5,a4,a3,a2,a1）
考虑递归算法，若只有一个结点，则直接返回，若存在两个结点（a1,a2）则需要做的操作有：　　　　　　a2->next=a1;a1->next=NULL;return a2;
a2即新的头结点，若有三个结点,则应先将子链（a2,a3）先逆置且返回该子链的新的头结点，然后把子链（a2,a3）当作一个复合结点a2',
组成新的二元组（a1,a2'）然后就可以执行前面相同的操作：a2'->next=a1;a1->next=NULL;return a3';即可，多个以上的结点可同理得到，
Node *Reverse(Node *head)
{
Node *p=head;
if(p==NULL)
return NULL;　　　　　//若是空链表，返回空
Node *q=p->next;
if(q==NULL)
return p;　　　　　//若只有一个结点，直接返回
else
head=Reverse(q);　　//记录子序列的新的头结点
q->next=p;　　　　　//当前结点与已经逆置的子序列看成是前后的两个结点p,q，作相应的逆置操作
p->next=NULL;
return head; 　　//返回新的子序列的头结点
}
2.用普通算法循环逆置（头插法重新建立带头结点的新链表）
Node *Reverse(Node *head)
{
Node *p=head->next;
if(p)//若链表不为空，则逆置，否则，空操作
{
　Node *q=p->next;
　　head->next=NULL;//头结点分离
　　while(p)
　　{
　　p->next=head->next;　//头插法建立链表
　　head->next=p;
　　if(q) //操作空指针的时候一定要非常注意，很容易出错
　　{
　　　p=q;
　　　q=p->next;
　　}
　　else
　　　break;
　　}
}
return head;
}

typedef struct ListNode{
ListNode *next;
Element data;
}ListNode, *pList;
这是我做的单链表逆序三个不同的算法，2个递归的以及一个非递归的

pList ReverseList( pList head ){
if( !head || !(head->next) )
return head;
pList ph = ReverseList( head->next );
head->next->next = head;
head->next = NULL;
return ph;
}
pList ReverseList( pList head , pList &tail ){
if( !head || !(head->next) ){
tail = head;
return head;
}
pList pt;
pList ph = ReverseList( head->next , pt );
pt->next = head;
head->next = NULL;
tail = head;
return ph;
}
pList ReverseListNonRec( pList head ){
if( !head || !(head->next) )
return head;
pList h = NULL,h1 = head;
while( head ){
h1 = head->next;
head->next = h;
h = head;
head = h1;
}
return h;
}

能够实现的方法都是好方法。

1

so？

---

西昌市18289454805： 怎样对单向链表进行就地逆置? - ？
程蝶克塞： /单链表的就地逆置 // 头插法: //先将头结点与链表的其他节点断开,然后利用头插法的原理将剩下的结点一次插到头结点的后面 //这样就实现了逆置 //由于通过形参可以改变主函数中的数值所以此处函数的类型可以设置为void类型 void ...

西昌市18289454805： 试写一算法,对单链表实现就地逆置 - ？
程蝶克塞： typedef struct list {int data; struct list * next;}*pList; void reverse(pList * root) { pList p1,p2=NULL,p3=NULL; p1=*root; while(p1) {p3=p2; p2=p1; p1=p1->next; p2->next=p3; }*root=p2; }

西昌市18289454805： 数据结构中如何实现单链表的就地逆置? - ？
程蝶克塞： 单链表

西昌市18289454805： 对单链表实行就地逆置算法? - ？
程蝶克塞： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21其实就是建立链表有的头插法 #define ElemType chartypedefstructNode{ElemType data;structNode *next; }Node,*LinkList;voidReverseList(LinkList L) {Node *p,*q;p = L->next; /*p为原链...

西昌市18289454805： 关于单链表的所有结点逆置 - ？
程蝶克塞： //就地逆置单链表//定义结点数据元素结构体 typedef struct snode { DataType x; struct snode *next; }SLNode;//逆置算法 void ListReverse(SLNode *head) { int i=-1,j; DataType x; SLNode *p,*q; p=head; while(p->next!=NULL&&i<(ListLength(head)-1)...

西昌市18289454805： 编写一个算法对带头结点的单链表实现就地逆置 - ？
程蝶克塞： struct LNode *insert(struct LNode *head,int x,int i) {int j=1;struct LNode *s,*q;q=head;s=(struct LNode *) malloc ( sizeof(struct LNode) );s->data=x; if(i==1){s->next=q;head=s;}else{while(q->next != NULL){q=q->next;j++;}if(j==i-1){...

西昌市18289454805： 数据结构用就地逆置的方法逆置单链表 - ？
程蝶克塞： Void exchange( linklist ha, linklist &hb){// (a1,a2,......an)==>(an,......,a2,a1) //ha:原链表的头指针,hb:逆置后新链表的头指针.两链表均不带头结点 node *p; hb=NULL; //新链表置初值 while (ha!=NULL) { p=ha; ha=ha->next; // 从原链表的表头中取出一个结点p p->next=hb; hb=p; // 将p插入到新链表的表头处 } }

西昌市18289454805： 用单链表作为存储结构写一实现就地逆置的算法 - ？
程蝶克塞： 完整的code如下:#include ＂stdio.h＂ #include＂malloc.h＂ typedef struct node { int data; struct node *next; }link; link *creat(int n) //创建链表 { link *head,*p,*s; int i; p=head=(link *)malloc(sizeof(link)); for(i=1;i<=n;i++) { s=(link *)malloc(sizeof(link)); ...

西昌市18289454805： 写一c语言算法,实现对单链表就地逆置. - ？
程蝶克塞： void inverse(LinkList &L) { LinkList h,p,q; q=L; p=h=L->next; //把q指向旧链表头,p,h指向第二个节点 while(p!=NULL) //倒置,把旧链表后一个节点的next指向前一个节点 { h->next=q; q=q->next; p=p->next; h=p; } L->next=NULL; //旧链表的头变成了新链表的尾,所以next为NULL L=h; //把L指向新链表的头 }

西昌市18289454805： 怎么编程 利用堆栈来进行单链表的就地逆置 - ？
程蝶克塞： for(p = list.begin();p!道=list.end();p=p->next) stack.push(p->key); for(p = list.begin();p!=list.end();p=p->next) { p->key = stack.top(); stack.pop(); }