合并两个排序的链表

剑指offer 链表合并算法

Created At : 2019-12-26 23:12

Count:641 Views 👀 :

Comment:

题目描述
思路
1. 构建一个新的链表
2. 将原来的链表改造，组合成一个新的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路

构建一个新的链表

尾插法构造新链表

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;
        ListNode* p3 = new ListNode(0);

        // 特殊情况处理
        if (p1 == nullptr && p2 != nullptr) return p2;
        if (p2 == nullptr && p1 != nullptr) return p1;
        if (p1 == nullptr && p2 == nullptr) return nullptr;
        // 两个非空单增链表合并
        ListNode* head = p3;
        while (p1 != nullptr && p2 != nullptr){
            while(p2 != nullptr && p1->val > p2->val){
//                cout<<"w1:p1->val = "<<p1->val<<",p2->val = "<<p2->val<<endl;
                p3->val = p2->val;
                p3->next = new ListNode(0);
                p3 = p3->next;
                p2 = p2->next;
            }
            while(p2 != nullptr && p1 != nullptr && p1->val <= p2->val){
//                cout<<"w2:p1->val = "<<p1->val<<",p2->val = "<<p2->val<<endl;
                p3->val = p1->val;
                p3->next = new ListNode(0);
                p3 = p3->next;
                p1 = p1->next;
            }
        }
        while (p1 == nullptr && p2 != nullptr) {
//            cout<<"w3: p2->val = "<<p2->val<<endl;
            p3->val = p2->val;
            p2 = p2->next;
            if (p2 != nullptr){
                p3->next = new ListNode(0);
                p3 = p3->next;
            }else{
                p3->next = nullptr;
            }
        }
        while (p1 != nullptr && p2 == nullptr) {
//            cout<<"w4: p1->val = "<<p1->val<<endl;
            p3->val = p1->val;
            p1 = p1->next;
            if (p1 != nullptr){
                p3->next = new ListNode(0);
                p3 = p3->next;
            }else{
                p3->next = nullptr;
            }
            
        }
        return head;
    }
};

将原来的链表改造，组合成一个新的链表

使用一个辅助头节点
将原来的两个链表按照大小链接起来

/**
 * 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 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        
        // 合并链表
        ListNode* newHead = new ListNode(-1);// 哨兵节点很重要
        ListNode* p0 = newHead;
        while(l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                p0->next = l1;
                l1 = l1->next;
            } else {
                p0->next = l2;
                l2 = l2->next;
            }
            p0 = p0->next;
        }
        p0->next = l1 == nullptr?l2:l1;
        
        return newHead->next;
        
    }
};

// 递归实现

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        
        // 递归算法
        if (l1==nullptr) {
            return l2;
        }
        if (l2==nullptr) {
            return l1;
        }
        
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com