c ++ 鏈表_C ++程序查找兩個單個鏈表的并集

c ++ 鏈表

Problem statement: Write a C++ program to find the union of two single linked lists.

問題陳述：編寫一個C ++程序來查找兩個單個鏈表的并集。

Example:

例： 

    Let the first linked list be:
5->4->3->6->1->NULL
Let the second linked list to be:
3->8->9->12->1->NULL
So there union is:
5->4->3->6->1->8->9->12->NULL

Solution

解

Brute force approach:

蠻力法：

One technique can be to include all the nodes of a linked list and for other linked check whether nodes are already appended or not. Such an approach takes O(m*n) times complexity. m, n=length of linked lists.

一種技術可以是包括鏈接列表的所有節點，而對于其他鏈接，請檢查節點是否已附加。 這種方法需要O(m * n)乘以復雜度 。 m ， n =鏈表的長度 。

Efficient approach:

高效的方法：

Efficient approach use to use merge sort.

高效的方法用于使用合并排序 。

  1. Sort both the linked list using merge sort. ( for detailed refer to: Merge sort for single linked lists)

    使用合并排序對兩個鏈表進行排序。 (有關詳細信息，請參閱： 合并單個鏈接列表的排序 )

  2. Scan each linked list and build union according to following:

    掃描每個鏈表并根據以下內容建立并集： 

  3. IF (list1->data < list2->data)
Createnode(list1->data) && append node to the union list
Traverse list1 by one step( list1=list1->next)
ELSE IF(list1->data ==list2->data)
Createnode(list1->data) && append nodeto the union list
Traverse list1 by one step( list1=list1->next)
Traverse list2 by one step( list2=list2->next)
ELSE//list1->data >list2->data
Createnode(list2->data) && append node to the union list
Traverse list2 by one step( list2=list2->next)
END IF-ELSE

  4. Display the union list

    顯示聯合列表

C ++實現查找兩個單個鏈表的并集 (C++ implementation to find Union of two single Linked Lists)

#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data; // data field
struct node *next;
};
void display(class node* head){
node* current=head; // current node set to head
while(current!=NULL){ //traverse until current node isn't NULL
printf("%d ",current->data);
current=current->next; // go to next node
}
}
node* creatnode(int d){
node* temp=(node*)malloc(sizeof(node));
temp->data=d;
temp->next=NULL;
return temp;
}
node* mergeList(node* split1,node* split2){
node* newhead=NULL;
//base cases
if(split1==NULL)
return split2;
if(split2==NULL)
return split1;
if(split1->data<=split2->data){
newhead=split1;
newhead->next=mergeList(split1->next,split2);
}
else{
newhead=split2;
newhead->next=mergeList(split1,split2->next);
}
return newhead;
}
void splitList(node* head,node** split1,node** split2){
node* slow=head;
node* fast=head->next;
while(fast!=NULL){
fast=fast->next;
if(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
}
*split1=head;
*split2=slow->next;
//spliting
slow->next=NULL;
}
void mergeSort(node** refToHead){
node* head=*refToHead;
node* split1,*split2;
//base case
if(head==NULL || head->next==NULL){
return;
}
//split the list in two halves
splitList(head,&split1,&split2);
//recursively sort the two halves
mergeSort(&split1);
mergeSort(&split2);
*refToHead=mergeList(split1,split2);
return;
}
node* findUnion(node* head1, node* head2){
if(head1==NULL && head2==NULL)
return NULL;
node* head3;
if(head1->data<head2->data){
head3=creatnode(head1->data);
head1=head1->next;
}
else if(head1->data==head2->data){
head3=creatnode(head1->data);
head1=head1->next;
head2=head2->next;
}
else{
head3=creatnode(head2->data);
head2=head2->next;
}
node* temp=head3;
while( head1!=NULL && head2!=NULL){
if(head1->data<head2->data){
temp->next=creatnode(head1->data);
temp=temp->next;
head1=head1->next;
}
else if(head1->data==head2->data){
temp->next=creatnode(head1->data);
temp=temp->next;
head1=head1->next;
head2=head2->next;
}
else{
temp->next=creatnode(head2->data);
temp=temp->next;
head2=head2->next;
}
}
while(head1!=NULL){
temp->next=creatnode(head1->data);
temp=temp->next;
head1=head1->next;
}
while(head2!=NULL){
temp->next=creatnode(head2->data);
temp=temp->next;
head2=head2->next;
}
return head3;
}
int main(){
printf("creating the linked list by inserting new nodes at the end\n");
printf("enter 0 to stop building the list, else enter any integer\n");
int k;
node* curr,*temp;
cout<<"enter list1...\n";
scanf("%d",&k);
node* head1=creatnode(k); //buliding list, first node
scanf("%d",&k);
temp=head1;
///inserting at the end//
while(k){
curr=creatnode(k);
temp->next=curr;//appending each node
temp=temp->next;
scanf("%d",&k);
}
cout<<"displaying list1...\n";
display(head1); // displaying the list
cout<<"\nenter list2...\n";
scanf("%d",&k);
node* head2=creatnode(k); //buliding list, first node
scanf("%d",&k);
temp=head2;
///inserting at the end//
while(k){
curr=creatnode(k);
temp->next=curr;//appending each node
temp=temp->next;
scanf("%d",&k);
}
cout<<"displaying list1...\n";
display(head2);
//sort both the lists
mergeSort(&head1);
mergeSort(&head2);
cout<<"\ndisplaying their union...\n";
node* head3=findUnion(head1,head2);
display(head3);
return 0;
}

Output

輸出量 

creating the linked list by inserting new nodes at the end
enter 0 to stop building the list, else enter any integer
enter list1...
5 4 3  6 1 0
displaying list1...
5 4 3 6 1
enter list2...
3 8 9 12 1 0
displaying list1...
3 8 9 12 1
displaying their union...
1 3 4 5 6 8 9 12

Example with explanation:

帶有說明的示例： 

First linked list: 5->4->3->6->1->NULL
Second linked list:3->8->9->12->1->NULL
After applying merge sort:
First linked list: 1->3->4->5->6->NULL
Second linked list: 1->3->8->9->12->NULL
---------------------------------------------------------
//for better understanding nodes are represented only by respective values
head1=1
head2=1
FindUnion(1,1):
0th iteration
head1!=NULL&&head2!=NULL
head1->data==head2->data //=1
thus head3(head of union list) =1
temp=head3=1
union list up to now:
1->NULL
head1=1->next=3;
head2=1->next=3;
1st iteration
head1!=NULL&&head2!=NULL
head1->data==head2->data //=3
thus temp->next =3
temp=temp->next=3;
union list up to now:
1->3->NULL
head1=3->next=4;
head2=3->next=8;
2nd iteration
head1!=NULL&&head2!=NULL
head1->data<head2->data //4<8
thus temp->next =head1->data=4
temp=temp->next=4;
union list up to now:
1->3->4->NULL
head1=4->next=5;
3rd iteration
head1!=NULL&&head2!=NULL
head1->data<head2->data //5<8
thus temp->next =head1->data=5
temp=temp->next=5;
union list up to now:
1->3->4->5->NULL
head1=5->next=6;
4th iteration
head1!=NULL&&head2!=NULL
head1->data<head2->data //6<8
thus temp->next =head1->data=6
temp=temp->next=6;
union list up to now:
1->3->4->5->6->NULL
head1=6->next=NULL;
5th iteration
head1 ==NULL
head2!=NULL
thus temp->next =head2->data=8
temp=temp->next=8;
union list up to now:
1->3->4->5->6->8->NULL
head2=8->next=9;
6th iteration
head1 ==NULL
head2!=NULL
thus temp->next =head2->data=9
temp=temp->next=9;
union list up to now:
1->3->4->5->6->8->9->NULL
head2=9->next=12;
7th iteration
head1 ==NULL
head2!=NULL
thus temp->next =head2->data=12
temp=temp->next=12;
union list up to now: 1->3->4->5->6->8->9->12->NULL
head2=12->next=NULL;
8th iteration:
head1==NULL 
head2==NULL
thus no more scanning, union list is built
union: 1->3->4->5->6->8->9->12->NULL
Head3 at 1

翻譯自: https://www.includehelp.com/cpp-programs/find-union-of-two-single-linked-lists.aspx

c ++ 鏈表

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/542229.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/542229.shtml
英文地址，請注明出處：http://en.pswp.cn/news/542229.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

精華版線段樹模板

精華版線段樹模板

哈哈哈&#xff0c;打了一上午。。。#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; ll a[10000010]; ll lazy[1000000]; …
閱讀更多...
【轉】unity地形插件T4M使用幫助

【轉】unity地形插件T4M使用幫助

unity的地形系統在手機游戲中因為效率問題基本無法使用&#xff0c;只能通過T4M這個地形插件來進行優化制作。下面大概講解一下使用流程及方法。 先中U3D里面用自帶的地形系統刷出想要的地形和貼圖。貼圖可以大概刷一下。后面要重新刷。 用導出腳本ExportTerrain.js導出地形為O…
閱讀更多...
ansys添加力矩_ANSYS軟件中施加扭矩的方法

ansys添加力矩_ANSYS軟件中施加扭矩的方法

ANSYS軟件中施加扭矩的方法胡意立&#xff0c;孫明禮&#xff0c;沈燕青&#xff0c;周佳杰&#xff0c;胡林強【摘要】在機械結構的有限元分析中&#xff0c;常會遇到施加扭矩的問題。文中探討了在ANSYS軟件中施加扭矩的一種方法&#xff0c;以在一個六棱柱一端施加扭矩為實例…
閱讀更多...
Python | 程序從列表中刪除重復的元素

Python | 程序從列表中刪除重復的元素

Example: 例&#xff1a; Input:list1: [10, 20, 10, 20, 30, 40, 30, 50]Output:List after removing duplicate elementslist2: [10, 20, 30, 40, 50]Logic: 邏輯&#xff1a; To implement the program is too easy, we have to append elements one by one to another…
閱讀更多...
Linux的簡介與虛擬機的管理

Linux的簡介與虛擬機的管理

Linux的簡介&#xff1a; 嚴格的來講&#xff0c;Linux不算是一個操作系統&#xff0c;只是一個Linux系統中的內核&#xff0c;Linux的全稱是GUN/Linux&#xff0c;這才算是一個真正意義上的Linux系統。 Linux是一個多用戶多任務的操作系統&#xff0c;擁有良好的用戶界面&…
閱讀更多...
python遞歸查找_Python程序使用遞歸查找數字的冪

python遞歸查找_Python程序使用遞歸查找數字的冪

python遞歸查找Given the base x and the power y and we have to find the x to the power y using recursion in Python. 給定基數x和冪y &#xff0c;我們必須使用Python中的遞歸找到x到冪y 。 By using recursion – We will be multiplying a number (initially with val…
閱讀更多...
phalapi可以依賴注入么_PHP 依賴注入

phalapi可以依賴注入么_PHP 依賴注入

通常調用一個類里面的方法需要如何操作&#xff1a;$class new class();$class->fun()依賴注入模式用來減少程序間的耦合依賴注入共有三種模式&#xff1a;setter 方法注入著重說下setter方法注入并結合ArrayAccess/*** Class Di* property People*/class Di implements Ar…
閱讀更多...
R語言：ggplot2精細化繪圖——以實用商業化圖表繪圖為例（轉）

R語言：ggplot2精細化繪圖——以實用商業化圖表繪圖為例（轉）

本文旨在介紹R語言中ggplot2包的一些精細化操作&#xff0c;主要適用于對R畫圖有一定了解&#xff0c;需要更精細化作圖的人&#xff0c;尤其是那些剛從excel轉ggplot2的各位&#xff0c;有比較頻繁的作圖需求的人。不討論那些樣式非常酷炫的圖表&#xff0c;以實用的商業化圖表…
閱讀更多...
Linux中常用的命令

Linux中常用的命令

1.文件建立 touch file&#xff08;文件的名字&#xff09; 注意&#xff1a; touch不但可以建立文件也可以修改文件的時間戳 時間戳分為&#xff1a; atime&#xff1a;文件內容被訪問的時間標識 mtime&#xff1a;文件內容被修改的時間標識 ctime&#xff1a;文件屬性或文件內…
閱讀更多...
藍橋杯寶藏排序題目算法(冒泡、選擇、插入)

藍橋杯寶藏排序題目算法(冒泡、選擇、插入)

冒泡排序: def bubble_sort(li): # 函數方式for i in range(len(li)-1):exchangeFalsefor j in range(len(li)-i-1):if li[j]>li[j1]:li[j],li[j1]li[j1],li[j]exchangeTrueif not exchange:return 選擇排序: 從左往右找到最小的元素&#xff0c;放在起始位置…
閱讀更多...
hive分區用2個字段有何限制_[特性]Hive動態分區功能使用

hive分區用2個字段有何限制_[特性]Hive動態分區功能使用

[特性]Hive動態分區功能使用2016-01-31 21:40說明Hive有兩種分區&#xff0c;一種是靜態分區&#xff0c;也就是普通的分區。另一種是動態分區。動態分區在數據導入時&#xff0c;會根據具體的字段值自行決定導入&#xff0c;并創建相應的分區。使用上更為方面。舉例準備工作創…
閱讀更多...
Linux系統中輸出輸入的管理

Linux系統中輸出輸入的管理

1.什么是輸入和輸出 輸入和輸出是計算機系統中的主機與外部進行通信的系統。它由外圍設備和輸入輸出控制系統兩部分組成&#xff0c;我們在shell中鍵入指令&#xff0c;然后送入CPU中運算產生結果&#xff0c;再將結果送到字符設備中顯示。簡單點來說輸入輸出就是通過我們的鍵盤…
閱讀更多...
find 命令示例_數組find（）方法以及JavaScript中的示例

find 命令示例_數組find（）方法以及JavaScript中的示例

find 命令示例JavaScript find()方法 (JavaScript find() method) find() method is used to get the first element from an array which passes the given test (condition). find()方法用于從通過給定測試(條件)的數組中獲取第一個元素。 Syntax: 句法&#xff1a; array.…
閱讀更多...
統計Apache或Nginx訪問日志里的獨立IP訪問數量的Shell

統計Apache或Nginx訪問日志里的獨立IP訪問數量的Shell

1、把IP數量直接輸出顯示&#xff1a; cat access_log_2011_06_26.log |awk ‘{print $1}’|uniq -c|wc -l 2、把IP數量輸出到文本顯示&#xff1a; cat access_log_2011_06_26.log |awk ‘{print $1}’|uniq -c|wc -l > ip.txt 總結&#xff1a;如果單個訪問日志大小超過2G…
閱讀更多...
ggplot2箱式圖兩兩比較_R繪圖 第四篇：繪制箱圖（ggplot2）

ggplot2箱式圖兩兩比較_R繪圖 第四篇：繪制箱圖（ggplot2）

箱線圖通過繪制觀測數據的五數總括&#xff0c;即最小值、下四分位數、中位數、上四分位數以及最大值&#xff0c;描述了變量值的分布情況。箱線圖能夠顯示出離群點(outlier)&#xff0c;離群點也叫做異常值&#xff0c;通過箱線圖能夠很容易識別出數據中的異常值。箱線圖提供了…
閱讀更多...
Linux系統中用戶的管理

Linux系統中用戶的管理

#####用戶管理###### 1在Linux中&#xff0c;有三種用戶&#xff1a; 1 root : 也成為超級用戶&#xff0c;對系統有控制權限&#xff0c;超級用戶可以不受限制的運行任何命令&#xff0c;root 用戶可以看作是系統的管理員。 2 系統用戶&#xff1a; 系統用戶通常為系統功能所必…
閱讀更多...
c# 命名空間命名規范_C＃命名空間能力問題和解答 套裝3

c# 命名空間命名規范_C＃命名空間能力問題和解答 套裝3

c# 命名空間命名規范1) There are following namespaces are given below, which is correct about "using" statement in C#.NET? In C#.Net, "using" statement is used to import the namespace in our programWe can create a new namespace with the…
閱讀更多...
shell 查出文件并復制到另一個文件夾

shell 查出文件并復制到另一個文件夾

找出所有大于100M的文件并展示出來find / -size 100M -exec ls -lh {} \;找出特定文件內大于200字節的文件并備份到另一個文件夾里去find /opt/test -type f -size 200c -exec cp {} /opt/test/cp/ \;轉載于:https://blog.51cto.com/406647516/1875417
閱讀更多...
correl函數相關系數大小意義_用Correl函數返回相關系數,以確定屬性關系

correl函數相關系數大小意義_用Correl函數返回相關系數,以確定屬性關系

我們辛辛苦苦制作了表格&#xff0c;當然是要作出分析的&#xff0c;肯定不能就是這么幾個數據吧。常用的分析法都是圖表&#xff0c;雖然看起來直觀&#xff0c;但是對于非作者來說&#xff0c;理解意思顯然不是那么方便。下面&#xff0c;教大家使用函數&#xff0c;來算出相…
閱讀更多...
Java之類的構造器（反射）

Java之類的構造器（反射）

反射&#xff1a; Java反射機制&#xff1a;指的是在Java程序運行狀態中,對于任何一個類,都可以獲得這個類的所有屬性和方法;對于給定的一個對象,都能夠調用它的任意一個屬性和方法。這種動態獲取類的內容以及動態調用對象的方法稱為反射機制。Java的反射機制允許在對類未知的情…
閱讀更多...
最新文章

Copyright @ 2022~2023