看图深入理解单链表的反转
如何把一个单链表进行反转?
方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。
方法2:使用3个指针遍历单链表,逐个链接点进行反转。
方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后,最后将第一个节点挪到新表的表尾。
方法4: 递归(相信我们都熟悉的一点是,对于树的大部分问题,基本可以考虑用递归来解决。但是我们不太熟悉的一点是,对于单链表的一些问题,也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树,因此可以考虑用递归来解决。或者说,因为单链表本身的结构也有自相似的特点,所以可以考虑用递归来解决)
方法1:
浪费空间。
方法2:
使用p和q两个指针配合工作,使得两个节点间的指向反向,同时用r记录剩下的链表。
p = head;
q = head->next;
head->next = NULL;
现在进入循环体,这是第一次循环。
r = q->next;
q->next = p;
p = q;
q =r;
第二次循环。
r = q->next
q->next = p;
p = q;
q = r
第三次循环。。。。。
具体代码如下
ActList* ReverseList2(ActList* head) { //ActList* temp=new ActList; if(NULL==head|| NULL==head->next) return head; //少于两个节点没有反转的必要。 ActList* p; ActList* q; ActList* r; p = head; q = head->next; head->next = NULL; //旧的头指针是新的尾指针,next需要指向NULL while(q){ r = q->next; //先保留下一个step要处理的指针 q->next = p; //然后p q交替工作进行反向 p = q; q = r; } head=p; // 最后q必然指向NULL,所以返回了p作为新的头指针 return head; }
updated 2014-01-24,重新非IDE环境写了一遍
如果觉得上面的先成环再断环的过程不太好理解,那么可以考虑下面这个办法,增加一个中间变量,使用三个变量来实现。
struct ListNode{ int val; ListNode* next; ListNode(int a):val(a),next(NULL){} }; ListNode* reverseLinkedList3(ListNode* head){ if(head==NULL||head->next==NULL) return head; ListNode* p=head; //指向head ListNode* r=head->next; //指向待搬运的节点,即依次指向从第2个节点到最后一个节点的所有节点 ListNode* m=NULL; //充当搬运工作用的节点 ListNode* tail=head->next; while(r!=NULL){ //bug2 循环语句写错了, while写成了if m=r; r=r->next; m->next=p->next; p->next=m; //if(r!=NULL) //std::cout<<"m="<<m->val<<" ,p="<<p->val<<" ,r="<<r->val<<std::endl; //else //std::cout<<"m="<<m->val<<" ,p="<<p->val<<" ,r=NULL"<<std::endl; } head=p->next; tail->next=p; p->next=NULL; tail=p; return head; // bug1 忘记了return }
方法3
还是先看图,
从图上观察,方法是:对于一条链表,从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后,(N-1)次这样的操作结束之后将第1个节点挪到新表的表尾即可。
代码如下:
ActList* ReverseList3(ActList* head) { ActList* p; ActList* q; p=head->next; while(p->next!=NULL){ q=p->next; p->next=q->next; q->next=head->next; head->next=q; } p->next=head;//相当于成环 head=p->next->next;//新head变为原head的next p->next->next=NULL;//断掉环 return head; }
附:
完整的链表创建,显示,反转代码:
//创建:用q指向当前链表的最后一个节点;用p指向即将插入的新节点。 //反向:用p和q反转工作,r记录链表中剩下的还未反转的部分。 #include "stdafx.h" #include <iostream> using namespace std; struct ActList { char ActName[20]; char Director[20]; int Mtime; ActList *next; }; ActList* head; ActList* Create() {//start of CREATE() ActList* p=NULL; ActList* q=NULL; head=NULL; int Time; cout<<"Please input the length of the movie."<<endl; cin>>Time; while(Time!=0){ p=new ActList; //类似表达: TreeNode* node = new TreeNode;//Noice that [new] should be written out. p->Mtime=Time; cout<<"Please input the name of the movie."<<endl; cin>>p->ActName; cout<<"Please input the Director of the movie."<<endl; cin>>p->Director; if(head==NULL) { head=p; } else { q->next=p; } q=p; cout<<"Please input the length of the movie."<<endl; cin>>Time; } if(head!=NULL) q->next=NULL; return head; }//end of CREATE() void DisplayList(ActList* head) {//start of display cout<<"show the list of programs."<<endl; while(head!=NULL) { cout<<head->Mtime<<"\t"<<head->ActName<<"\t"<<head->Director<<"\t"<<endl; head=head->next; } }//end of display ActList* ReverseList2(ActList* head) { //ActList* temp=new ActList; if(NULL==head|| NULL==head->next) return head; ActList* p; ActList* q; ActList* r; p = head; q = head->next; head->next = NULL; while(q){ r = q->next; // q->next = p; p = q; // q = r; // } head=p; return head; } ActList* ReverseList3(ActList* head) { ActList* p; ActList* q; p=head->next; while(p->next!=NULL){ q=p->next; p->next=q->next; q->next=head->next; head->next=q; } p->next=head;//相当于成环 head=p->next->next;//新head变为原head的next p->next->next=NULL;//断掉环 return head; } int main(int argc, char* argv[]) { // DisplayList(Create()); // DisplayList(ReverseList2(Create())); DisplayList(ReverseList3(Create())); return 0; }
方法4: 递归
updated: 2014-01-24
因为发现大部分问题都可以从递归角度想想,所以这道题目也从递归角度想了想。
现在需要把A->B->C->D进行反转,
可以先假设B->C->D已经反转好,已经成为了D->C->B,那么接下来要做的事情就是将D->C->B看成一个整体,让这个整体的next指向A,所以问题转化了反转B->C->D。那么,
可以先假设C->D已经反转好,已经成为了D->C,那么接下来要做的事情就是将D->C看成一个整体,让这个整体的next指向B,所以问题转化了反转C->D。那么,
可以先假设D(其实是D->NULL)已经反转好,已经成为了D(其实是head->D),那么接下来要做的事情就是将D(其实是head->D)看成一个整体,让这个整体的next指向C,所以问题转化了反转D。
上面这个过程就是递归的过程,这其中最麻烦的问题是,如果保留新链表的head指针呢?想到了两个办法。
// 递归版的第一种实现,借助类的成员变量m_phead来表示新链表的头指针。 struct ListNode{ int val; ListNode* next; ListNode(int a):val(a),next(NULL){} }; class Solution{ ListNode* reverseLinkedList4(ListNode* head){ //输入: 旧链表的头指针 if(head==NULL) return NULL; if(head->next==NULL){ m_phead=head; return head; } ListNode* new_tail=reverseLinkedList4(head->next); new_tail->next=head; head->next=NULL; return head; //输出: 新链表的尾指针 } ListNode* m_phead=NULL;//member variable defined for reverseLinkedList4(ListNode* head) };
第二个办法是,增加一个引用型参数 new_head,它用来保存新链表的头指针。
struct ListNode{ int val; ListNode* next; ListNode(int a):val(a),next(NULL){} }; class Solution{ ListNode* reverseLinkedList5(ListNode* head, ListNode* & new_head){ //输入参数head为旧链表的头指针。new_head为新链表的头指针。 if(head==NULL) return NULL; if(head->next==NULL){ new_head=head; //当处理到了旧链表的尾指针,也就是新链表的头指针时,对new_head进行赋值。因为是引用型参数,所以在接下来调用中new_head的值逐层传递下去。 return head; } ListNode* new_tail=reverseLinkedList5(head->next,new_head); new_tail->next=head; head->next=NULL; return head; //输出参数head为新链表的尾指针。 } };
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对猪先飞的支持。
相关文章
- 这篇文章主要介绍了C#使用自定义算法对数组进行反转操作的方法,涉及C#针对数组操作的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要为大家详细介绍了C语言单链表实现多项式相加,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了Python 实现反转整数的案例(很容易懂的那种),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-10
ASP.NET Core依赖注入系列教程之控制反转(IoC)
这篇文章主要给大家介绍了关于ASP.NET Core依赖注入系列教程之控制反转(IoC)的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-09-22- 这篇文章主要介绍了基于Python实现2种反转链表方法代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-07-06
Java实现单链表SingleLinkedList增删改查及反转 逆序等
单链表是链表的其中一种基本结构。一个最简单的结点结构如图所示,它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素,指针域用于指向下一个具有相同结构的结点。因为只有一个指针结点,称为单链表...2021-10-15- 这篇文章主要为大家详细介绍了C++使用模板实现单链表的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要给大家介绍了关于利用C++简单实现顺序表和单链表的方法,文中给出了详细的示例代码供大家参考学习,需要的朋友可以参考借鉴,下面来跟着小编一起来学习学习吧。...2020-04-25
- 这篇文章主要介绍了C++ 数字的反转实现实例的相关资料,需要的朋友可以参考下...2020-04-25
- 以下是对使用递归和非递归方式反转单向链表的示例进行了详细的分析介绍,需要的朋友可以过来参考下...2020-04-25
- 今天小编就为大家分享一篇c语言实现两个单链表的交叉合并方式,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 本篇文章主要介绍了详解三种C#实现数组反转方式,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 这篇文章主要介绍了理解Java 中的IOC控制反转,具有一定参考价值,需要的朋友可以了解下,希望能够给你带来帮助...2021-10-12
- 这篇文章主要介绍了C语言实现单链表实现方法的相关资料,链表分为单向链表、双向链表、循环链表,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言创建和操作单链表数据结构的实例教程,讲解使用C语言实现链表结构时指针的使用,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了python反转一个三位整数的多种实现方案,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-10
- 本篇文章是对单链表的快速排序进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要为大家详细介绍了C++使用模板实现单链表,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C语言单链表常见操作,需要的朋友可以参考下...2020-04-25
- PS怎样才能做出两个颜色相反的图片?小编给大家带来了一篇教程,很轻松就能做出反转颜色的两张图片。 LOGO的颜色一般都比较简单,所以要将LOGO的颜色反转的步骤并不复...2016-12-15