C++怎么合并兩個(gè)有序鏈表

這篇文章主要講解了“C++怎么合并兩個(gè)有序鏈表”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C++怎么合并兩個(gè)有序鏈表”吧！

目錄

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

• 思路

• 代碼

• 鏈表Listnode詳細(xì)介紹

  
  

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

示例 1：

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

輸出：[1,1,2,3,4,4]

示例 2：

輸入：l1 = [], l2 = []

輸出：[]

示例 3：

輸入：l1 = [], l2 = [0]

輸出：[0]

思路

可以簡單理解為： 同時(shí)遍歷兩個(gè)鏈表， 當(dāng)前遍歷的結(jié)點(diǎn)，誰的結(jié)點(diǎn)小，就把誰的結(jié)點(diǎn)“摘下來”，“安裝”在新鏈表上就可以了吧。

這里為了簡單方便的處理， 給新鏈表先“安裝”一個(gè)頭結(jié)點(diǎn)

代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 使用帶頭結(jié)點(diǎn)的鏈表解決問題
        // 待輸出鏈表的頭部
        ListNode* head = new ListNode;  //節(jié)點(diǎn)是個(gè)指針，需要new來開辟空間
        // 待輸出鏈表的 last 結(jié)點(diǎn)
        ListNode* last = head;   //last和head是一個(gè)東西，只是為了最后輸出的時(shí)候找到head
        while(l1 != nullptr && l2 != nullptr){  //循環(huán)條件
            if(l1->val < l2->val){
                last->next = l1;    //last->next指向l1
                l1 = l1->next;      //將l1的下一個(gè)節(jié)點(diǎn)改為l1
            }
            else{
                last->next = l2;
                l2 = l2->next;
            }
            last = last->next;   //將last的下一個(gè)節(jié)點(diǎn)改為last
        }
         // l1 或 l2 可能還有剩余結(jié)點(diǎn)沒有合并， 
        // 由于從上面的 while 循環(huán)中退出， 那么鏈表 l1 和 l2 至少有一個(gè)已經(jīng)遍歷結(jié)束
        if(l1 != nullptr){
            last->next = l1;
        }
        else if(l2 != nullptr){
            last->next = l2;
        }
        return head->next;
    }
};

鏈表Listnode詳細(xì)介紹

Listnode定義 。

struct ListNode {
       int val;    //定義val變量值，存儲節(jié)點(diǎn)值
       struct ListNode *next;   //定義next指針，指向下一個(gè)節(jié)點(diǎn)，維持節(jié)點(diǎn)連接
  }

1.節(jié)點(diǎn)存儲了兩個(gè)變量：value 和 next。

value 是這個(gè)節(jié)點(diǎn)的值，

next 是指向下一節(jié)點(diǎn)的指針，

當(dāng) next 為空指針時(shí)，這個(gè)節(jié)點(diǎn)是鏈表的最后一個(gè)節(jié)點(diǎn)。

2.注意val只代表當(dāng)前指針的值，

比如p->val表示p指針的指向的值；

而p->next表示鏈表下一個(gè)節(jié)點(diǎn)，也是一個(gè)指針。

3.構(gòu)造函數(shù)包含兩個(gè)參數(shù) _value 和 _next ，分別用來給節(jié)點(diǎn)賦值和指定下一節(jié)點(diǎn)

感謝各位的閱讀，以上就是“C++怎么合并兩個(gè)有序鏈表”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對C++怎么合并兩個(gè)有序鏈表這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！