c++ 如何合并两个有序链表

合并两个有序链表是一个经典的算法问题。下面将详细讲解使用C++解决这个问题的完整攻略。

问题描述

合并两个有序链表为一个新的有序链表。

解决思路

迭代法

迭代法的思路是：比较两个链表的节点，将较小的节点加入合并后的链表，直到有一个链表为空。此时将另一个非空链表节点全部加入合并后的链表即可。

递归法

递归法的思路是：比较两个链表的头部，较小的节点加入合并后的链表，然后继续递归下去，更新链表头，直到有一个链表为空。此时将另一个非空链表节点全部加入合并后的链表即可。

选择使用哪种方法取决于个人喜好和算法效率。通常来说，迭代法的效率要高于递归法。

代码实现

迭代法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummyHead(0);
        ListNode* tail = &dummyHead;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }             
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummyHead.next;
    }
};

递归法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    }
};

示例代码

#include <iostream>
#include <vector>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummyHead(0);
        ListNode* tail = &dummyHead;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }             
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummyHead.next;
    }
};

void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Solution s;
    vector<int> nums1 = {1, 3, 5, 7};
    vector<int> nums2 = {2, 4, 6, 8};
    ListNode* l1 = new ListNode(0);
    ListNode* l2 = new ListNode(0);
    ListNode* p = l1;
    for (int num : nums1) {
        p->next = new ListNode(num);
        p = p->next;
    }
    p = l2;
    for (int num : nums2) {
        p->next = new ListNode(num);
        p = p->next;
    }
    ListNode* merged = s.mergeTwoLists(l1->next, l2->next);
    printList(merged); // 1 2 3 4 5 6 7 8
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    }
};

void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Solution s;
    vector<int> nums1 = {1, 3, 5, 7};
    vector<int> nums2 = {2, 4, 6, 8};
    ListNode* l1 = new ListNode(0);
    ListNode* l2 = new ListNode(0);
    ListNode* p = l1;
    for (int num : nums1) {
        p->next = new ListNode(num);
        p = p->next;
    }
    p = l2;
    for (int num : nums2) {
        p->next = new ListNode(num);
        p = p->next;
    }
    ListNode* merged = s.mergeTwoLists(l1->next, l2->next);
    printList(merged); // 1 2 3 4 5 6 7 8
    return 0;
}