使用遞歸的方法，同時記錄每次取出元素的鏈表，就可以實現這個功能 。具體程序如下：
首先，建立鏈表的結構體：
struct?ListNode?{int?val;
ListNode?*next;
ListNode(int?x)?:?val(x),?next(NULL)?{}
};
然後，合並鏈表的主程序：
ListNode?*mergeTwoLists(ListNode?*l1,?ListNode?*l2,bool?flag){
if?(l1?==?NULL)
return?l2;
else?if?(l2?==?NULL)
return?l1;
ListNode?*Head;
if?(flag?==?true){
flag?=?false;
Head?=?new?ListNode(l1->val);
Head->next?=?mergeTwoLists(l1->next,?l2,flag);
}
else{
flag?=?true;
Head?=?new?ListNode(l2->val);
Head->next?=?mergeTwoLists(l1,?l2->next,flag);
}
return?Head;
}
最後，測試的程序：
void?testcode(){
int?arr1[6]?=?{?1,?4,?6,?8,?30,?45?};
int?arr2[3]?=?{?5,?10,?15?};
ListNode?l1(1);
ListNode?*p?=?&l1;
for?(int?i?=?1;?i?<?6;?i++)
{
p->next?=?new?ListNode(arr1[i]);
p?=?p->next;
}
ListNode?l2(5);
p?=?&l2;
for?(int?i?=?1;?i?<?3;?i++)
{
p->next?=?new?ListNode(arr2[i]);
p?=?p->next;
}
bool?flag?=?true;
ListNode?*newHead?=?mergeTwoLists(&l1,?&l2,?flag);
while?(newHead!=?NULL)
{
cout?<<?newHead->val?<<?"?";
newHead?=?newHead->next;
}
cout?<<?endl;
}
運行結果如下：