内容简介:链表通常有单链表,双链表和循环链表,是面试里面常涉及到的考点。链表的结构简单,但是涉及到指针的操作,容易出现新的理解,其中也牵涉到许多小的细节的考虑。题目描述:定义一个函数,输入一个链表的头结点,求反转后该链表的输出和链表的头结点。链表结点定义如下:
链表通常有单链表,双链表和循环链表,是面试里面常涉及到的考点。链表的结构简单,但是涉及到指针的操作,容易出现新的理解,其中也牵涉到许多小的细节的考虑。
面试题:反转链表
题目描述:定义一个函数,输入一个链表的头结点,求反转后该链表的输出和链表的头结点。
链表结点定义如下:
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 }
以上所述就是小编给大家介绍的《面试题目:反转链表的算法实现》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 图解算法:单链表两两反转(眼睛会了手就会系列)
- 算法 – 有效地反转字符数组中的单词(而不是字符)的顺序
- Go数组反转练习
- LeetCode (206):反转链表
- LeetCode (206):反转链表
- leetcode 206 反转链表
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。