面试题目:反转链表的算法实现

栏目: 编程工具 · 发布时间: 5年前

内容简介:链表通常有单链表,双链表和循环链表,是面试里面常涉及到的考点。链表的结构简单,但是涉及到指针的操作,容易出现新的理解,其中也牵涉到许多小的细节的考虑。题目描述:定义一个函数,输入一个链表的头结点,求反转后该链表的输出和链表的头结点。链表结点定义如下:

链表通常有单链表,双链表和循环链表,是面试里面常涉及到的考点。链表的结构简单,但是涉及到指针的操作,容易出现新的理解,其中也牵涉到许多小的细节的考虑。

面试题:反转链表

题目描述:定义一个函数,输入一个链表的头结点,求反转后该链表的输出和链表的头结点。

链表结点定义如下:


1 struct ListNode {
2     int val;
3     struct ListNode *next;
4     ListNode(int x) :
5             val(x), next(NULL) {               //构造函数
6     }
7 };


 

分析:

链表前后元素的关联就是通过指针实现的,每个链表都有一个next指针指向下一个结点,末尾的节点的next域则置NULL;

反转链表就是要求修改指针的指向。下面的图就是反转前和反转后的效果。

反转前:

面试题目:反转链表的算法实现

反转后:

面试题目:反转链表的算法实现

下面来实现如何对链表进行反转。

假设我们现在正在对结点3进行反转操作,即原来结点2的next域指向j结点3(图中已经调整完毕,现在指向前一个结点),结点3的next域指向结点4。现在要做的是将结点3的next域指向结点2。从图中我们可以看出,当把结点3的next指针指向结点2的同时,原先指向的4就已经无法被正常的访问到了,为了避免“断链”,我们必须在指针更改指向之前,保存修改结点的下一结点。同时我们也必须存储上一个结点,因为next域即将修改指向该结点。因此定义三个指针,分别指向当前遍历的结点,前一个结点和后一个结点。

算法实现如下:

 
 1 ListNode* ReverseList(ListNode* pHead)
 2 {
 3     ListNode* pReversedHead = NULL;
 4     ListNode* pNode = pHead;
 5     ListNode* pPrev = NULL;
 6     while(pNode != NULL)
 7     {
 8         ListNode* pNext = pNode->next;
 9 
10         if(pNext == NULL)
11             pReversedHead = pNode;
12 
13         pNode->next = pPrev;
14 
15         pPrev = pNode;
16         pNode = pNext;
17     }
18 
19     return pReversedHead;
20 }
 

当然使用下面这样想法也是可以的,两者的思路一致,没有差别。只不过下面的代码必须注意一点,跳出while循环的时候,最后一个结点的next域指向前一个结点,否则就会导致“断链”。

 
 1     ListNode* ReverseList(ListNode* pHead) {
 2         ListNode *base=pHead; 
 3         ListNode *pre=NULL;  
 4         ListNode *pnext=NULL;
 5         if(pHead==NULL) return NULL; 
 6     while(base->next){  
 7         pnext=base->next;   
 8         base->next=pre;      
 9         pre=base;       
10         base=pnext;     
11     }    
12         base->next=pre; 
13         return base; 
14     } 
 

以上所述就是小编给大家介绍的《面试题目:反转链表的算法实现》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

程序员修炼之道

程序员修炼之道

Andrew Hunt、David Thomas / 马维达 / 电子工业出版社 / 2005-1 / 48.00元

《程序员修炼之道》由一系列的独立的部分组成,涵盖的主题从个人责任、职业发展,直到用于使代码保持灵活、并且易于改编和复用的各种架构技术。利用许多富有娱乐性的奇闻轶事、有思想性的例子以及有趣的类比,全面阐释了软件开发的许多不同方面的最佳实践和重大陷阱。无论你是初学者,是有经验的程序员,还是软件项目经理,本书都适合你阅读。一起来看看 《程序员修炼之道》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具