商量:將兩個鏈表非降序歸並為一個鏈表並仍然有序的完成辦法。本站提示廣大學習愛好者：（商量:將兩個鏈表非降序歸並為一個鏈表並仍然有序的完成辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是商量:將兩個鏈表非降序歸並為一個鏈表並仍然有序的完成辦法正文
已知兩個鏈表list1和list,2，各自非降序分列，將它們歸並成別的一個鏈表list3，而且仍然有序，請求保存一切節點。
完成進程中，list1中的節點和list2中的節點都轉移到了list3中，留意泛型的友元函數的用法。
法式若有缺乏的地方，還望斧正！！！
界說List類
#include "stdafx.h"
#include <iostream>
using namespace std;
template<class T>
struct Node
{
T data;
Node<T> * next;
};
template <class T>
class MyList
{
public:
//結構函數，初始化一個頭結點，data為空，next指向第一個節點
MyList()
{
phead = new Node<T>;
phead->data = NULL;
phead->next = NULL;
}
//析構函數，將全部鏈表刪除,這裡采取的是正序撤消
~MyList()
{
Node<T>* p;
p = phead;
while (p)
{
Node<T>* q;
q = p;
p = p->next;
delete q;
}
}
//復制結構函數
MyList(MyList& mylist)
{
Node<T>* q = mylist.phead->next;
Node<T>* pb = new Node<T>;
this->phead = pb;
while (q != NULL)
{
Node<T>* p = new Node<T>;
p->data = q->data;
p->next = NULL;
pb->next = p;
pb = p;
q = q->next;
}
}
//拔出一個元素的辦法,在第i個元素拔出一個元素e，
//前往值為NOTE<T>型指針，指向拔出的誰人元素
Node<T>* Insert(int i, T e)
{
//在鏈表的第i個地位，拔出一個元素e
int j = 0;
Node<T>* p;
p = phead;
while (p && j < i - 1)
{
p = p->next;
++j;
}
if (!p || j > i -1)
{
return phead;
}
Node<T>* q;
q = new Node<T>;
q->data = e;
q->next = p->next;
p->next = q;
return q;
}
//輸入list中的元素
void Show()
{
Node<T> *p = phead->next;
while (NULL != p)
{
cout << p->data << " ";
p = p->next;
}
}
template<class T> friend void MergeList(MyList<T> &list1, MyList<T> &list2, MyList<T> &list3);
private:
Node<T>* phead;};
<PRE class=cpp name="code">// </PRE><PRE class=cpp name="code">//將兩個鏈表歸並成一個鏈表，而且仍然有序。辦法保存了歸並之前list1和list2的節點，
//歸並以後list1和list2消逝。將list1和list2歸並為list3
template<class T>
void MergeList(MyList<T> &list1, MyList<T> &list2, MyList<T> &list3)
{
Node<T> *head1 = list1.phead, *head2 = list2.phead;
Node<T> *head3 = list3.phead, *temp = NULL;
if (head1->next == NULL)
{//假如list1為空，則list3頭指針指向list2
head3 = head2;
list2.phead->next = NULL;//將list2清除，避免析構函數析構list2時找不到對象
}
else if (head2->next == NULL)
{//假如list1為空，則list3頭指針指向list2
head3 = head1;
list1.phead->next = NULL;//將list1清除，避免析構函數析構list2時找不到對象
}
head1 = head1->next;
list1.phead->next = NULL;//將list1清除，避免析構函數析構list2時找不到對象
head2 = head2->next;
list2.phead->next = NULL;//將list2清除，避免析構函數析構list2時找不到對象
if (head1->data < head2->data)
{//假如list1的第一個元素小於list2的第一個元素
head3->next = head1;//將list1的第一個元素接到list3上
head1 = head1->next;
}
else
{
head3->next = head2;//將list2的第一個元素接到list3上
head2 = head2->next;
}
temp = head3->next;//指向list3以後最初一個節點
while (head1 != NULL && head2 != NULL)
{
if (head1->data < head2->data)
{
temp->next = head1;//將list1中的元素接到list3的前面
temp = head1;
head1 = head1->next;
}
else
{
temp->next = head2;//將list2中的元素接到list3的前面
temp = head2;
head2 = head2->next;
}
}
if (NULL == head1) //將list1或許list2中的殘剩部門接到list3的前面
{
temp->next = head2;
}
else if (NULL == head2)
{
temp->next = head1;
}
}<PRE class=cpp name="code"> </PRE><PRE class=cpp name="code">//主函數</PRE><PRE class=cpp name="code">int _tmain(int argc, _TCHAR* argv[])
{
MyList<int> list1, list2, list3;
for (int i = 1; i <= 10; i ++)
{
list1.Insert(i, 3*i);
list2.Insert(i, 2*i);
}
MergeList(list1, list2, list3);
list3.Show();
return 0;
}</PRE><BR>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
</PRE>
