題目

將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。

示例 ：
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]

思路

• 創(chuàng)建一個新的鏈表頭節(jié)點（dummyNode）和一個指針current，用于表示當(dāng)前節(jié)點。

• 在一個while循環(huán)中，比較兩個鏈表的節(jié)點值，并依次將較小值的節(jié)點連接到新鏈表上。具體的步驟如下：

  • 如果list1的節(jié)點值小于等于list2的節(jié)點值，那么將current的next指針指向list1，并將list1指針后移一位。
  • 否則，將current的next指針指向list2，并將list2指針后移一位。
  • 然后，將current指針后移一位。

• 當(dāng)循環(huán)結(jié)束時，說明至少有一個鏈表已經(jīng)遍歷完畢。我們需要將剩余未遍歷完的鏈表連接到新鏈表的末尾。具體的步驟如下：

  • 如果list1還有剩余節(jié)點，將current的next指針指向list1。
  • 如果list2還有剩余節(jié)點，將current的next指針指向list2。

• 最后，返回dummyNode的next指針，即為合并后的新鏈表的頭節(jié)點。

通過以上步驟，我們可以將兩個升序鏈表合并為一個新的升序鏈表。該算法的時間復(fù)雜度為O(m+n)，其中m和n分別為兩個鏈表的長度。

Code:文章來源地址http://www.zghlxwxcb.cn/news/detail-830809.html

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 創(chuàng)建一個新的鏈表頭節(jié)點
        ListNode dummyNode(0);
        ListNode* current = &dummyNode;

        // 比較兩個鏈表的節(jié)點值，依次將較小值的節(jié)點連接到新鏈表上
        while (list1 && list2) {
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }

        // 將剩余未遍歷完的鏈表連接到新鏈表上
        if (list1) {
            current->next = list1;
        }
        if (list2) {
            current->next = list2;
        }

        return dummyNode.next; // 返回新鏈表的頭節(jié)點
    }
};

到了這里，關(guān)于LeetCode21.合并兩個有序鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！