关于倒置链表的四种方法详解，总有一种适合你 |
您所在的位置：网站首页 › 双向循环链表逆置 › 关于倒置链表的四种方法详解，总有一种适合你 |
关于倒置链表的四种方法详解，总有一种适合你
|
单链表反转的四种方法
未反转的链表是这样的：
简单点来说：迭代反转法的思路就是连续创立三个指针，beg、mid、end，遍历整个链表，在遍历期间，改变指针的指向，使他们指向前一个数据域。三个指针的最初指向与图一相同，具体做法与下面相同。
这里只需要改变mid的指针指向即可，，最后改变head的指针指向，使其与mid相同。 link * iteration_reverse(link* head) { if(head->next==NULL||head==NULL) return head; else { link * beg=NULL; link * mid=head; link * end=head->next; while(1) { mid->next=beg; if(end==NULL) { break; } beg=mid; mid=end; end=end->next; } head=mid; return head; } } 2、递归反转链表这种方法我也是学习了好久才学习明白的，所以先给大家奉上代码,并且进行注释之后再去进行讲解： link* recursive_reverse(link* head) { if(head==NULL||head->next==NULL)//特殊情况的考虑 { return head; } else { link * new_head=recursive_reverse(head->next); head->next->next=head; head->next=NULL; return new_head; } } 由于 head 不为 NULL，因此函数每执行到第 11 行时，递归都会深入一层，并依次将指向节点 2、3、4 的指针作为实参（head_next 的指向）参与递归。而根据递归出口的判断条件，当函数参数 head 指向的是节点 4 时满足 head->next == NULL，递归过程不再深入，并返回指向节点 4 的指针，这就是反转链表的新头指针。因此，当递归首次退出一层时，new_head 指向的是节点 4 ，而 head 由于退出一层，指向的是节点 3， 在此基础上，开始执行 17、18 行代码，整个操作过程如图 9 所示，最后将 new_head 的指向继续作为函数的返回值，传给上一层的 new_head。 再退一层，此时 new_head 仍指向节点 4，而 head 退出一层后，指向的是节点 2。在此基础上执行 17、18 行代码，并最终将 new_head 的指向作为函数返回值，继续传给上一层的 new_head。 再退一层，此时 new_head 仍指向节点 4，而 head 退出一层后，指向的是节点 1。在此基础上执行 17、18 行代码，并返回 new_head。（此方法不建议大家使用，废头发）图解如下：
所谓的头插法是指在链表的原有基础上，创立一个新的链表，依次将链表头部的节点拿下，置于新的链表头节点之后，此即为头插法。 下面就是关于头插法的图示讲解：
关于头插法的代码如下： link * head_reverse(link * head) { link * new_head=NULL; link * temp=NULL; if(head==NULL||head->next==NULL) { return head; } while(head!=NULL) { temp=head; head=head->next; temp->next=new_head; new_head=temp; } return new_head; } 4、就地逆置反转链表此方法和头插法很相似，唯一的区别就在于此方法不用重新建立一个新的链表，而是直接的对于原来的链表进行修改，从而实现了对于链表的反转，但是需要额外借助两个指针 图解如下：
代码如下： link * local_reverse(link * head) { link * beg=NULL; link * end=NULL; if(head==NULL||head->next==NULL) { return head; } else{ beg=head; end=head->next; } while(end!=NULL) { beg->next=end->next; end->next=head; head=end; end=beg->next; } return head; } 总结本节仅以无头节点的链表为例，讲解了实现链表反转的 4 种方法。实际上，对于有头节点的链表反转： 使用迭代反转法实现时，初始状态忽略头节点（直接将 mid 指向首元节点），仅需在最后一步将头节点的 next 改为和 mid 同向即可；使用头插法或者就地逆置法实现时，仅需将要插入的节点插入到头节点和首元节点之间即可；递归法并不适用反转有头结点的链表（但并非不能实现），该方法更适用于反转无头结点的链表。做这些花了我一个下午的时间，值不值得你为我点一波小小的关注，这么帅气的你点个赞再走呗 |
【本文地址】
今日新闻 |
推荐新闻 |