在C++中通过递归方法实现单链表倒置

初始化列表

struct ListNode{
	int val;
	LiseNode* next;
	ListNode(int x) :val(x),next(NULL){}
};

遍历

void query_node(){
	node *p=head;
	while(p!=NULL){
		cout<<p->data<<' ';
		p=p->nxt;
	}
	cout<<endl;
}

建表（尾部插入）

void build_node(){
	head=NULL,tail=NULL;
	for(int i=1;i<=5;i++){
		int x;
		cin>>x;
		node *tmp=new node(x);
		if(head==NULL) head=tail=tmp;
		else {
			tail->nxt=tmp;
			tail=tmp;
		}
	} 
}

倒置（递归）

图解

好的，以下是这部分代码的图解：

假设原始链表为：1 -> 2 -> 3 -> 4 -> NULL

1. reverseList(1) 调用
   • head = 1, head->next = 2
   • 递归调用 reverseList(2)，返回倒置后的头结点 newHead = 4
2. reverseList(2) 调用
   • head = 2, head->next = 3
   • 递归调用 reverseList(3)，返回倒置后的头结点 newHead = 4
3. reverseList(3) 调用
   • head = 3, head->next = 4
   • 递归调用 reverseList(4)，返回倒置后的头结点 newHead = 4
4. reverseList(4) 调用
   • head = 4, head->next = NULL
   • 返回 head 作为倒置后的头结点
5. 回到 reverseList(3)
   • 将 head->next->next = head，即 4 -> 3
   • 将 head->next = NULL，即 3 -> NULL
   • 返回 newHead = 4 作为倒置后的头结点
6. 回到 reverseList(2)
   • 将 head->next->next = head，即 3 -> 2
   • 将 head->next = NULL，即 2 -> NULL
   • 返回 newHead = 4 作为倒置后的头结点
7. 回到 reverseList(1)
   • 将 head->next->next = head，即 2 -> 1
   • 将 head->next = NULL，即 1 -> NULL
   • 返回 newHead = 4 作为倒置后的头结点
8. 完成递归调用，返回倒置后的链表头结点 newHead = 4

因此，最终倒置后的链表为：4 -> 3 -> 2 -> 1 -> NULL

node *reverse_node(node *now){
	if(now->nxt==NULL) return now;
	node *newhead=reverse_node(now->nxt);
	now->nxt->nxt=now;
	now->nxt=NULL;
	return newhead;
}

完整代码

1.精简版

#include<bits/stdc++.h>
using namespace std;
struct node{
	int data;
	node *nxt;
	node(int x) : data(x),nxt(NULL){}
}; 
node *head,*tail;
void query_node(){
	node *p=head;
	while(p!=NULL){
		cout<<p->data<<' ';
		p=p->nxt;
	}
	cout<<endl;
}
void build_node(){
	head=NULL,tail=NULL;
	for(int i=1;i<=5;i++){
		int x;
		cin>>x;
		node *tmp=new node(x);
		if(head==NULL) head=tail=tmp;
		else {
			tail->nxt=tmp;
			tail=tmp;
		}
	} 
}
node *reverse_node(node *now){
	if(now->nxt==NULL) return now;
	node *newhead=reverse_node(now->nxt);
	now->nxt->nxt=now;
	now->nxt=NULL;
	return newhead;
}
int main(){
	build_node();
	cout<<"original node:";
	query_node();
	head=reverse_node(head); //注意要把head指向新的首节点 
	cout<<"After reverse:";
	query_node();
	return 0;
}

2.详细注释版

#include <iostream>
using namespace std;

// 定义链表结点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {} 
};


// 递归函数，实现链表倒置
ListNode* reverseList(ListNode* head) {
    // 如果链表为空或者只有一个结点，则直接返回
    if (head->next == NULL) {
        return head;
    }

    // 递归调用，获取倒置后的链表头结点
    ListNode* newHead = reverseList(head->next);

    // 将当前结点插入到倒置后链表的末尾
    head->next->next = head;
    head->next = NULL;

    return newHead;
}

// 初始化链表，从键盘输入五个数据依次插入链表尾部
ListNode* initList() {
    ListNode* head = NULL;
    ListNode* tail = NULL;
    for (int i = 0; i < 5; i++) {
        int x;
        cin >> x;
        ListNode* node = new ListNode(x); //这里必须使用new 
        if (head == NULL) {
            head = node;
            tail = node;
        }
        else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

int main() {
    // 初始化链表
    ListNode* head = initList();

    // 输出原始链表
    cout << "Original List: ";
    ListNode* p = head;
    while (p) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    // 倒置链表
    head = reverseList(head);

    // 输出倒置后的链表
    cout << "Reversed List: ";
    p = head;
    while (p) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    return 0;
}