题目描述 牛客网

• 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的

题目解读

• 剑指Offer 145

代码

#include<iostream>
using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};

class Solution {
public:

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(!pHead1){
            return pHead2;
        }
        else if(!pHead2){
            return pHead1;
        }

        ListNode *p = NULL;
        if(pHead1 -> val < pHead2 -> val){
            p = pHead1;
            p -> next = Merge(pHead1 -> next, pHead2);
        }
        else{
            p = pHead2;
            p -> next = Merge(pHead1, pHead2 -> next);
        }
        return p;
    }


    ListNode* create(int *array, int len){
        ListNode *p;
        ListNode *head = NULL;
        ListNode *tail = NULL;

        for(int i=0; i < len; i++){
            p = new ListNode(array[i]);

            if(!head){
                head = p;
            }
            else{
                tail -> next = p;
            }
            tail = p;
        }

        return head;
    }

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

main(){
    Solution ss;
    ListNode *head1 = NULL;
    ListNode *head2 = NULL;
    ListNode *head3 = NULL;

    int a[] = {1, 3, 5, 7};
    int len1 = sizeof(a)/sizeof(a[0]);
    head1 = ss.create(a, len1);
    ss.print_Node(head1);

    int b[] = {2, 4, 6, 8};
    int len2 = sizeof(b)/sizeof(b[0]);
    head2 = ss.create(b, len2);
    ss.print_Node(head2);

    head3 = ss.Merge(head1, head2);
    ss.print_Node(head3);
}

2023.5.25代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1) return pHead2;
        if (!pHead2) return pHead1;
        if (pHead1->val <= pHead2->val) {
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        } else {
            pHead2->next = Merge(pHead1, pHead2->next);
            return pHead2;
        }
    }
};

总结展望

• 递归的思想，要好好把握啊