本文目录
- 链表的就地逆置是什么意思
- 把单向链表中元素逆置（不允许申请新的结点空间）
- 什么叫单链表就地逆置
- 单链表就地逆置的两种方法(递归与普通循环)
- 链表就地逆置p->next=head->next意思
- 单链表的逆置,帮我解释一下这个算法,void reverse (LinkList
- 如何用c语言实现单链表的逆置
链表的就地逆置是什么意思
就是指的不需要使用别的辅助空间来存放原链表中的各个结点的数据元素，只是重新修改各个链表结点的链接域的指向，最后达到原来处于第一位的成了表尾，原来最后的表尾变成了表头
把单向链表中元素逆置（不允许申请新的结点空间）
设first指针指向单链表的第一个结点，试设计一个算法，通过遍历一趟链表，将链表中//所有结点的链接方向逆转，并使first指针指向逆转后的第一个结点处(即原来的最后一个结点处),//若原来链表空，则返回false.(说明：first指针是类SingleList的成员变量，是Node《T》为类的一个指针，Node类的定义为：classNode{Tdata;Node《T》*link;friendclassSingleList《T》};//函数原型为：template《classT》boolSingleList《T》::Reverse();template《classT》boolSingleList《T》::Reverse(){if(!first)returnfalse;Node《T》*p=first,*q;first=NULL;while(p){q=p;p-》link=first;first=p;p=q;}returntrue;}
什么叫单链表就地逆置
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个位置。这样就实现了带头结点的单链表的就地逆置。
单链表就地逆置的两种方法(递归与普通循环)
一、用递归算法 对于不带头结点的单链表（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; //返回新的子序列的头结点 } 二、用普通算法循环逆置（头插法重新建立带头结点的新链表） ***隐藏网址***
链表就地逆置p->next=head->next意思
注意head每次指向哪个节点head-》next总是指向已经经过逆置的最后一个节点，也就是新的经过逆置的头节点所以每次完成一个新的节点的逆置，要将其next指向上一个逆置的节点，刚好是head-》next指向的节点比如原来有链表 A-》B-》C-》D-》NULL开始head-》next = A, head-》next-》next=B首先让p=A,并让A-》next=NULL, 也就是让A成为尾节点然后q指向B，此时head-》next还是指向A的，也就是刚刚完成逆置的节点while开始之后每次都将q赋值给p，于是 p=B, q =C, B-》next=head-》next = A, head-next = B此时head-》next指向B，刚好又是刚完成逆置的节点以后继续循环
单链表的逆置,帮我解释一下这个算法,void reverse (LinkList
voidreverse(LinkList&L)//单链表的逆置{\x09LinkLista,b,c;a=L;b=L-》next;//L为头结点\x09while(b-》next!=NULL)//主要思想就在这了,从第一个结点开始,只要\x09{它的下一个结点不为NULL,则将-》next反\x09\x09c=b-》next;向,先将-》next保存,再反指\x09\x09b-》next=a;\x09\x09a=b;//这两名循环上面\x09\x09b=c;\x09}\x09b-》next=a;//-》next为空的话,由于后面没了,直接反向\x09L-》next-》next=NULL;//L-》next此时指向的是反向前的第一个结点,反向后这个结点改为指向NULL,即收尾\x09L-》next=b;//头结点指向第一个结点}//描述的可能不是很清楚,你画个链表图的话应该有助于理解
如何用c语言实现单链表的逆置
扣着的是头节点（头子）
车是首节点（首子）
马是次节点（次子）
牙签细的是指针指向，香头发黑的是指向，铁头细的是指向。
根据步骤写程序的伪算法（3步4循环，7张图片搞定），如下：
以下是while循环（条件：香头指向不为空）
第一个循环把马弄到车前面，
第二个循环把相弄到马前面
第三个循环把士弄到相前面
........
直到香指向为空后停止循环。
代码如下：只需要一个首结点pHead,就能把链表找到，并倒置。具体代码如下
p香=pHead-》pNext;
p铁=p香-》pNext;
p香-》pNext=NULL;
P香=p铁
while(p香 ！=NULL)
{
p铁=p香-》pNext;
p香-》pNext=pHead-》pNext;
pHead-》pNext=p香；
p香=p铁；
}
对照伪算法（三步四循环），和上面的代码是一一对应的：
第一步：香头指向首子，铁头指向次子
第二步：删掉首子指向次子（铁头所指向的那个子）的牙签
第三步：香头跟着铁头
以下循环条件：（条件：香头指向不为空）
{
循环1：铁头移动到香头的下一个指向
循环2：香头的下一个指向首子
循环3：头子的下一个跟着香头
循环4：香头跟着铁头
}
自己用道具操作几遍，然后把流程背会，以后自己根据流程写代码即可。
