如何在 C++ 中递归拆分 k 个节点后的链表？

Question

我有一个普通链表：

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

我需要编写一个递归函数，将在 k 个元素之后通过引用传递的给定链表分成 2 个，将前 k 个节点留在该列表中，return将第二个列表与其余的节点。

我的迭代解决方案如下所示：

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

这似乎工作得很好。现在我真的想不出一个递归的解决方案。我正在尝试：

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;

}

这显然是错误的，因为它 returning x 到 L->next 所以两个列表都变成 1 2 3 4 5 6.

如何为此编写递归函数？参数和 return 类型应该保持不变。如果有人可以解释我如何将我的迭代解决方案转换为递归解决方案，那也很棒。

Answer 1

您目前有

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;
}

你想要这样的东西

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);
}

注意这个和你原来的守卫 k 大于列表的长度。

单功能版：

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);
}

Answer 2

起初我没有看到通过引用传递列表指针的意义，但后来我发现它是实现的关键。

我认为你可以这样做：

检查空输入列表；可能是要求您将输入列表拆分到超出其末尾的位置 (k > list size)。
检查 k == 0；这是进行拆分的要点，因此 1) return 当前 head 和 2) 将前一个节点的 next 指针设置为空（如果这是第一次调用，则设置列表指针本身);您只需将 head 设置为 null，因为 head 是对您在调用 split_list.
否则，递归调用split_list。

[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);
}

如何在 C++ 中递归拆分 k 个节点后的链表？

How to recursively split a linked list after k nodes in C++?

c++

recursion

function

linked-list

nodes