C++中链表交替拆分的递归方法
给定一个单向链表作为输入。目标是将列表拆分为两个单链表，它们具有原始列表的备用节点。如果输入列表有节点a→b→c→d→e→f那么在分裂之后，两个子列表将是a→c→e和b→d→f。
我们将采用两个指针N1和N2，一个指向原始列表的头部，另一个指向头部→next。现在将两个指针移动到下一个节点的下一个并创建子列表。
例子
输入 -列表：-1→5→7→12→2→96→33
输出 -原始列表：1571229633
列表1：17233
列表2：51296
说明 -从1和5开始，下一个指向备用节点以创建如上所示的子列表。
输入 -列表：-13→53→90→18→44→11→99→32
输出 -原始列表：1353901844119932
列表1：13904499
列表2：53181132
说明-从13和53开始，下一个指向备用节点以创建如上所示的子列表。
下面程序中使用的方法如下
在这种方法中，我们将采用两个指针N1和N2，一个指向原始列表的头部，另一个指向头部→next。现在将两个指针移动到下一个节点的下一个并创建子列表。
取结构体Node与int数据部分和Node作为下一个指针。
函数addtohead(Node**head,intdata)用于向头部添加节点以创建单向链表。
使用上述函数创建一个单向链表，将head作为指向第一个节点的指针。
函数display(Node*head)用于打印从头节点开始的链表。
取两个节点指针node1和node2。
函数splitList(Node*head,Node**n1,Node**n2)获取节点指针并将n1指向head和n2指向head→原始字符串的next。
在里面调用split(*n1,*n2)将原始列表拆分为两个子列表
函数split(Node*N1,Node*N2)接受N1和N2指针并创建两个包含原始列表交替节点的子列表。
如果N1和N2都为空，则不返回任何内容。
如果N1→next不为空，则设置tmp=N1->next->next和N1->next=tmp；
fN2→next不为空然后设置tmp=N2->next->next和N2->next=tmp;
调用split(N1->next,N2->next);用于下一次迭代。
最后使用display().
示例
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void addtohead(Node** head, int data){
Node* nodex = new Node;
nodex->data = data;
nodex->next = (*head);
(*head) = nodex;
}
void split(Node* N1, Node* N2){
Node *tmp;
if (N1 == NULL || N2 == NULL){
return;
}
if (N1->next != NULL){
tmp=N1->next->next;
N1->next = tmp;
}
if (N2->next != NULL){
tmp=N2->next->next;
N2->next = tmp;
}
split(N1->next, N2->next);
}
void splitList(Node* head, Node** n1, Node** n2){
*n1 = head;
*n2 = head->next;
split(*n1, *n2);
}
void display(Node* head){
Node* curr = head;
if (curr != NULL){
cout<<curr->data<<" ";
display(curr->next);
}
}
int main(){
Node* head = NULL;
Node *node1 = NULL, *node2 = NULL;
addtohead(&head, 20);
addtohead(&head, 12);
addtohead(&head, 15);
addtohead(&head, 8);
addtohead(&head, 10);
addtohead(&head, 4);
addtohead(&head, 5);
cout<<"原始清单："<<endl;
display(head);
splitList(head, &node1, &node2);
cout<<endl<<"清单1： ";
display(node1);
cout<<endl<<"清单2： ";
display(node2);
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出
原始清单： 5 4 10 8 15 12 20 清单1： 5 10 15 20 清单2： 4 8 12