leetcode21 Merge Two Sorted Lists 將兩個(gè)有序鏈表組合成一個(gè)新的有

BothEyes1993 發(fā)布于2019-08-14 18:05 / 2208人閱讀

摘要：題目要求翻譯過來就是將兩個(gè)有序的鏈表組合成一個(gè)新的有序的鏈表思路一循環(huán)在當(dāng)前兩個(gè)鏈表的節(jié)點(diǎn)都是非空的情況下比較大小，較小的添入結(jié)果鏈表中并且獲得較小節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

題目要求

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

翻譯過來就是：將兩個(gè)有序的鏈表組合成一個(gè)新的有序的鏈表

思路一：循環(huán)

在當(dāng)前兩個(gè)鏈表的節(jié)點(diǎn)都是非空的情況下比較大小，較小的添入結(jié)果鏈表中并且獲得較小節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。這樣比較直至至少遍歷完一個(gè)鏈表。再將剩下的鏈表添至結(jié)果鏈表的末端

public class MergeTwoSortedLists_21 {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode start = new ListNode(0);
        ListNode temp = new ListNode(0);
        start.next = temp;
        while(l1!=null && l2!=null){
            if(l1.val <= l2.val){
                temp.next = l1;
                l1 = l1.next;
            }else{
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        if(l1!=null){
            temp.next = l1;
        }
        if(l2!=null){
            temp.next = l2;
        }
        return start.next.next;
    }
    
    public class ListNode{
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}

思路二：遞歸

每次比較得到兩個(gè)節(jié)點(diǎn)中較小的節(jié)點(diǎn)作為結(jié)果返回，并繼續(xù)對剩下來的鏈表重新獲得較小節(jié)點(diǎn)。

public class MergeTwoSortedLists_21 {
    public ListNode mergeTwoLists_recursive(ListNode l1, ListNode l2){
        if(l1==null){
            return l2;
        }else if (l2==null){
            return l1;
        }
        ListNode mergeHead;
        if(l1.val <= l2.val){
            mergeHead = l1;
            mergeHead.next = mergeTwoLists_recursive(l1.next, l2);
        }else{
            mergeHead = l2;
            mergeHead.next = mergeTwoLists(l1, l2.next);
        }
        return mergeHead;
    }
    
    public class ListNode{
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會(huì)不定期的發(fā)放福利哦~