I have an ordinary linked list with:

struct node{
  int info;
  node* next;
};

I need to write a recursive function that splits in 2 a given linked list passed by reference after k elements, leaving the first k nodes in this list and returning the second list with the rest of the nodes.

My iterative solutions looks like this:

node* split(node*&L, int k){
   node* M;
   node* head = L;
   while(k>1){
      head=head->next;
      k--;
   }
   M = head->next;
   head->next = NULL;
   return M;
}


Output:
L: 1 2 3 4 5 6 
after split with: k = 3
L: 1 2 3 
M: 4 5 6 

Which seems to work just fine. Now i can't really think of a recursive solution for this. I was trying with:

node* splitL(node*&L, int k){
   if(!L) return 0;
   if(k<=1){
      node* x = L->next;
      L->next =  NULL;
      return x;
   }
   L->next = splitL(L->next, k-1);
   return L;

}

Which is obviously wrong because it's returning x into L->next so both lists become 1 2 3 4 5 6.

How do I write a recursive function for this? The parameters and the return type should stay the same. Also it would be great if someone could explain how I could translate my iterative solution to a recursive one.

CodePudding user response：

You currently have

node* split(node*&L, int k){
   node* M;
   node* head = L;
   while(k>1){
      head=head->next;
      k--;
   }
   M = head->next;
   head->next = NULL;
   return M;
}

You want something like

node* split(node*&L, int k){
   node* M;
   node* head = splitPoint(L, k);
   M = head->next;
   head->next = NULL;
   return M;
}

node* splitPoint(node*&L, int k){
   if (k <= 0)
     return L;
   return splitPoint(L->next, k - 1);
}

Note neither this nor your original guards for k greater than the length of the list.

Single-function version:

node* split(node*&L, int k){
   if (k <= 0)
   {
     node* head = L;
     node* M = head->next;
     head->next = NULL;
     return M;
   }
   return split(L->next, k - 1);
}

CodePudding user response：

At first I didn't see the point of passing your list pointer by reference, but then I found out it is the clue of the implementation.

I think you could do this:

• Check for a null input list; it could be that you were asked to split the input list beyond the end of it (k > list size).
• Check for k == 0; this is the point to do the split, so 1) return the current head and 2) set previous node's next pointer to null (or the list pointer itself if this were the first call); you do that just setting head to null, because head is a reference to the pointer you used in the call to split_list.
• Otherwise, call split_list recursively.

[Demo]

node* split_list(node*& head, int k)
{
    if (!head) { return nullptr; }
    if (k == 0) { node* ret{head}; head = nullptr; return ret; }
    return split_list(head->next, k-1);
}