单链表递归_头歌顺序递归单链表

1.前言

以前觉得递归太麻烦，指针方便多了，于是乎单链表的题目都是用迭代呀，双指针呀来做的。这次突破下自己，将单链表的递归掰扯一下，等下会用一个简单的小题目来作为例子；

2.平常递归

我先讲一下平常递归的流程，方便待会单链表递归的理解；
题目：输入一个数字 N=123，打印出1，2，3；
代码：

void print(n)
{
if(n>9)
print(n/10);
printf("%d\n",n%10);
}
1
2
3
4
5
6

运行流程图：

3.链表递归

链表递归其实也是一样的，都是形成函数的栈桢，然后释放栈桢；
题目：题目链接
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

先上代码

 struct ListNode* reverseList(struct ListNode* head){
 if(head==NULL||head->next==NULL);//传进来空链表或者只剩一个则不需要进行反转了
 return head;
 struct ListNode* ans= reverseList(struct ListNode* head->next);//传入下一个节点的地址
 head->next->next=head;//下一个节点的next变成前面这个节点的地址
 head->next=NULL;//前面这个节点的next变为NULL；
 return ans;
 }
1
2
3
4
5
6
7
8

图文解析：