如何合并兩個(gè)有序鏈表

如何合并兩個(gè)有序鏈表？相信很多人都還沒(méi)學(xué)會(huì)這個(gè)技能，通過(guò)這篇文章的總結(jié)，希望你能學(xué)會(huì)合并兩個(gè)有序鏈表。如下資料是關(guān)于合并兩個(gè)有序鏈表的兩種方法。

直接合并

因?yàn)橐呀?jīng)有序了,類似歸并排序中的合并一樣,操作不難,直接上代碼了.

ListNode t = new ListNode(0);
ListNode head = t;
while(l1 != null && l2 != null)    
{
    if(l1.val < l2.val)
    {
        t.next = l1;
        l1 = l1.next;
    }
    else
    {
        t.next = l2;
        l2 = l2.next;
    }
    t = t.next;
}
while(l1 != null)
{
    t.next = l1;
    l1 = l1.next;
    t = t.next;
}
while(l2 != null)
{
    t.next = l2;
    l2 = l2.next;
    t = t.next;
}
return head.next;

遞歸合并

這個(gè)可以采用遞歸優(yōu)化,而且不用額外設(shè)置一個(gè)移動(dòng)的臨時(shí)結(jié)點(diǎn)t.首先對(duì)兩個(gè)指針進(jìn)行判空操作,其中一個(gè)為空的話返回另一個(gè),然后進(jìn)行遞歸合并,首先創(chuàng)建一個(gè)head結(jié)點(diǎn),進(jìn)行賦值后遞歸合并next結(jié)點(diǎn),將返回值賦給head.next,最后返回head.

if(l1 == null) return l2;
if(l2 == null) return l1;

ListNode head = null;
if(l1.val < l2.val)
{
    head = l1;
    head.next = mergeTwoLists(l1.next, l2);
}
else
{
    head = l2;
    head.next = mergeTwoLists(l1, l2.next);
}
return head;

看完上述內(nèi)容，你們掌握合并兩個(gè)有序鏈表的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！