反转单链表（递归方式）

题目描述

用递归的方式反转长度为N的单链表。

输入

第一行输入一个整数，表示输入单链表的长度

第二行输入要插入的单链表元素值

输出

输出反转后的单链表节点值

样例输入

5
1 2 3 4 5

样例输出

5 4 3 2 1

#include
using namespace std;typedef struct LNode{int data;struct LNode *next;LNode(int data):data(data),next(NULL){};
}LNode,*LinkList;LinkList CreateLinkList(int len){//尾插法建立单链表LNode *L = new LNode(-1);int val;//用于接收输入的值 LNode *p;//定义一个指针p用于接收输入的结点 LNode *tail = L;while(len--) {scanf("%d",&val);p = new LNode(val);tail->next = p;tail = tail->next;}tail->next = NULL;return L;
}
LinkList Reverse(LinkList &L){//将链表L用递归算法逆转 if(L == NULL){return NULL;//若输入节点为空，返回NULL }if(L->next == NULL){return L;}//终止条件（递归出口），当递归到尾结点的时候，返回尾结点（也就是链表逆转后的头元素结点） LNode *head = Reverse(L->next);//递归逆转L之后的链表 LNode *p = L->next;//记录当前处理节点的后继 p->next = L;//让其后继的next域指向前一个结点，实现逆转 L->next = NULL;//让当前处理的结点的next域为空（不能缺这一句，否则会形成环，形成死循环 ） return head;
}
int main(void){int len;scanf("%d",&len);LinkList L = CreateLinkList(len);L->next = Reverse(L->next);//传入头节点的下一个结点LNode *p = L->next;while(p != NULL) {printf("%d ",p->data);p=p->next;}return 0;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！