下面的功能是我正在尝试处理的功能。我遇到的问题是我不知道如何将指向原始头的指针“保留”到列表中，因为这是插入后我必须返回的内容。
没有驱动程序代码，因此一切都必须在该函数内完成。
因为我必须递归地执行此操作，所以我不能只创建一个临时节点来指向原始头。我刚刚习惯递归，找不到解决方案。
注意：我的函数还存在一些其他问题，因为我相信它不能很好地将新节点插入到链表的开头和结尾，但我相信我可以解决这些边缘情况。
我想学习的主要内容是如何“存储”列表的原始头部。
感谢所有帮助。
Node* insert(Node* head, int index, int data)
{
if (head == NULL) return NULL; // if list is empty
if (index == 1) // if we have accessed node before insertion
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->next = head->next; // new_node->next now links to the node next in the list
head->next = new_node; // head->next links to new node
new_node->data = data; // assigns new node its data
return head; // not sure how to return original head
}
return insert(head->next, index - 1, data);
}
Node *insertRecursive(Node* head,int pos,int val)
{
if(pos==0 || head==NULL)
{
Node *newNode= new Node(val);
newNode->next=head;
head=newNode;
return head;
}
else
head->next = insertRecursive(head->next,pos-1,val);
}
对于初学者来说，指定节点插入位置的参数应该是无符号整数类型，例如
size_t0该函数可以通过以下方式定义
struct Node * insert( struct Node *head, size_t pos, int data )
{
if (head == NULL || pos == 0 )
{
struct Node *new_node = malloc( sizeof( struct Node ) );
new_node->next = head;
new_node->data = data;
head = new_node;
}
else
{
head->next = insert( head->next, pos - 1, data );
}
return head;
}
这是一个演示程序
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
struct Node * insert( struct Node *head, size_t pos, int data )
{
if (head == NULL || pos == 0)
{
struct Node *new_node = malloc( sizeof( struct Node ) );
new_node->next = head;
new_node->data = data;
head = new_node;
}
else
{
head->next = insert( head->next, pos - 1, data );
}
return head;
}
void print( const struct Node *head )
{
for (; head != NULL; head = head->next)
{
printf( "%d -> ", head->data );
}
puts( "null" );
}
int main( void )
{
struct Node *head = NULL;
head = insert( head, 0, 3 );
print( head );
head = insert( head, 0, 0 );
print( head );
head = insert( head, 1, 1 );
print( head );
head = insert( head, 2, 2 );
print( head );
}
程序输出为
3 -> null
0 -> 3 -> null
0 -> 1 -> 3 -> null
0 -> 1 -> 2 -> 3 -> null
Node* insert_Node_recursively(Node* 头,int 数据,int 位置){
//Inserting on the first node.
if(position==0){
Node* newNode=new Node(data);
newNode->next=head;
head=newNode;
return head;
}
if((head->next==NULL && position==0) /*for adding on the end of the list */ || position==1 /*Inserting on node in between */){
Node* newNode=new Node(data);
newNode->next=head->next;
head->next=newNode;
return head;
}
//in case the position exceeds the total number of nodes
if(head->next==NULL && position>0){
return head;
}
else{
head->next=insert_Node_recursively(head->next,data,position-1);
}
return head;
}
我认为这会起作用，涵盖了所有方面
//here is the full solution to add a node recursively at a position
#include<iostream>
using namespace std;
//the below code is for creation of class for node
class Node
{
public:
int data;
Node * next;
Node(int data) //constructor
{
this -> data = data;
next = NULL;
}
};
//the below code is for creation of linked list
//a terminator -1 is used to stop taking input
Node * takeInput()
{
int data;
cout<<"Enter the data of the node to be inserted ( use -1 to terminate
the insertion ) : ";
cin>>data;
Node * head = NULL;
Node * tail = NULL;
while(data != -1)
{
Node * newNode = new Node(data);
if(head == NULL)
{
head = newNode;
tail = newNode;
}
else
{
tail->next=newNode;
tail = tail -> next;
}
cout<<"Enter the data of the node to be inserted ( use -1 to
terminate the insertion ) : ";
cin>>data;
}
return head;
}
//the below code is to print the linked list
void print(Node * head)
{
if(head == NULL)
{
cout<<"The linked list id empty !"<<endl;
return;
}
Node * temp = head;
while(temp != NULL)
{
cout<<temp->data<<" ";
temp = temp -> next;
}
cout<<endl;
}
//the below part is the main solution to the problem
//insertion at a position using recursion
Node * insertRecursive(Node * head, int data , int key)
{
if (head == NULL || key == 0)
{
Node * newNode = new Node(data);
newNode -> next = head;
head = newNode;
}
else
{
head -> next = insertRecursive(head -> next , data , key - 1);
}
return head;
}
//this is the main from where all the function calls happen
int main()
{
int data, key;
Node * head = takeInput();
print(head);
cout<<"Enter the data of the node to be inserted : ";
cin>>data;
cout<<"Enter the position of insertion : ";
cin>>key;
head = insertRecursive(head,data,key);
print(head);
}
//if you have created a node using class then here is the solution
//to insert a node at a position recursively
Node * insertRecursive(Node * head, int data , int key)
{
if (head == NULL || key == 0)
{
Node * newNode = new Node(data);
newNode -> next = head;
head = newNode;
}
else
{
head -> next = insertRecursive(head -> next , data , key - 1);
}
return head;
}