Rumah > Artikel > pembangunan bahagian belakang > 使用递归和非递归实现单链反转详解
本篇文章讲述了使用递归以及非递归如何实现单链反转,可能有很多同学并不太了解单链反转是什么,那么就让我们废话少说,直接看本篇文章吧!
在题目中给出了可使用递归与迭代两种算法的提示。
因为对递归理解不深刻,首先采用迭代编写算法,在题目中的head结点认为是含有数据的第一个结点
题目思路:从头结点出发,向后遍历,按照顺序一个个逐渐实现结点之间链的反转。
首先尝试使用2个指针完成操作,失败
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* pre = NULL; while(head -> next) { pre = head; head = head -> next; head -> next = pre; } return head; };
理由如下:在反转过程中,head ->next 已经反向,无法继续向后遍历,因此增加一个指针采用3个指针完成操作
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* pre = NULL; while(head) { ListNode* next = head -> next; head -> next = pre;//head是尾结点,指针置空 head = next; pre = head; } return pre; //head = NULL };
递归不会,参考Discuss后,理解。
思路如下:通过递归使得头结点不断向后遍历,直到终止条件:达到尾结点 后停止。
代码如下:
class Solution { public: ListNode* reverseList(ListNode* head) { //终止条件,达到尾结点停止 if(head == NULL || head ==NULL) return head; else { //头结点向后移动 ListNode* temp = reverList(head->next); head->next->next = head; //1 head->next = NULL; //2 } return temp; };
到达递归终止条件时呈现的状态如下:
返回上一层递归后状态如下:
经过注释1、2的两行代码后,状态如下
可见head结点的位置与递归层数有关,而temp作为反转后的头结点,位置始终不动,从而达到反转效果。
递归代码虽能看懂,然而我现在还并不会设计,还是个菜鸡。
相关文章:
Atas ialah kandungan terperinci 使用递归和非递归实现单链反转详解. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!