数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中链表交替分割的递归方法
给定一个单向链表作为输入。目标是将列表拆分为两个单向链表，这两个链表包含原始列表的交替节点。如果输入列表的节点为 a → b → c → d → e → f，则拆分后，两个子列表将为 a → c → e 和 b → d → f。
我们将使用两个指针 N1 和 N2，一个指向原始列表的头部，另一个指向头部 → next。现在将这两个指针移动到下一个节点，并创建子列表。
示例
输入 - 列表：1 → 5 → 7 → 12 → 2 → 96 → 33
输出 - 原始列表：1 5 7 12 2 96 33
列表 1：1 7 2 33
列表 2：5 12 96
说明 - 从 1 和 5 开始，下一个指向交替节点以创建上面所示的子列表。
输入 - 列表：13 → 53 → 90 → 18 → 44 → 11→ 99 → 32
输出 - 原始列表：13 53 90 18 44 11 99 32
列表 1：13 90 44 99
列表 2：53 18 11 32
说明 - 从 13 和 53 开始，下一个指向交替节点以创建上面所示的子列表。
下面程序中使用的方案如下
在这种方法中，我们将使用两个指针 N1 和 N2，一个指向原始列表的头部，另一个指向 head→ next。现在将这两个指针移动到下一个节点，并创建子列表。
使用 int 数据部分和 Node 作为下一个指针的结构 Node。
函数 addtohead(Node** head, int data) 用于将节点添加到头部以创建单向链表。
使用上述函数创建单向链表，其中 head 为指向第一个节点的指针。
函数 display(Node* head) 用于打印从头节点开始的链表。
使用两个 Node 指针 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;
如果 N2→ 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<<"Original List :"<<endl;
display(head);
splitList(head, &node1, &node2);
cout<<endl<<"List 1: ";
display(node1);
cout<<endl<<"List 2: ";
display(node2);
return 0;
}输出
如果我们运行上述代码，它将生成以下输出
Original List : 5 4 10 8 15 12 20 List 1: 5 10 15 20 List 2: 4 8 12
305 次查看
