資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
