单链的快速逆置
1.首先我们应建立一个链表:
struct list{ int data; list* next; }; 这里用图解给出所建立的链表
然后用一个空的节点来指向我们链表的头结点,这个新节点存放
的数据为空,引用这个空节点来方便对后面的倒置进行操作
2.接下来是对链的倒置.
对每个元素来说,对应next的成员所存放的地址应该转移到原先链的下下一个元素的next中去,这样就完成了下下一个节点的逆置, 那么对应原先的链,我们应该从链首元素的上上一个元素所对应的next成员来找到链首的next成员的数值.而我们的链首元素的上上 一个元素不存在,所以我们将NULL赋值给首元素,而每次在赋值之前,我们应该将现有元素的next成员的值用一个中间变量保存起来 从而方便接下来的赋值操作. 在知道了如何进行转换之后,就可以写出如下代码:
list* x = NULL; // 每次用来存储现有元素的NEXT的值 list* p = NEW->next; // 用来遍历原来的链 list* y; // 用来存放下一个要逆置的元素的首地址 while ( p ){ // 对循环进行判断,只要p不为空,就会对进行下一次逆置 y = p->next; // 先存好下一个要逆置的元素的首地址 p->next = x; // 改变现有元素的next成员 x = p; //存放下下一个元素的首地址,在下一次循环中赋值给对应元素的next成员 p = y; // 跟新循环判断条件并指向向下一个要逆置的元素 } NEW->next = x; // 要注意在完成逆置之后要将NEW元素的next改成逆置前的链的末元素的首地址 这样我们就完成了整个单链的快速逆置,只进行了一些地址的交换,而并没有繁琐的运算
