剑指Offer-合并两个排序的链表

发表于 | 分类于

题目描述

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

解题思路

想不到自己做对了，没遇到什么因为指针而错误的坑！算是一个小小的进步吧。虽然有个地方，因为我不知道动态内存怎么申请的，所以一开始有点卡，struct申请：ListNode* head = new ListNode(0); 这是在有构造函数的情况下，若没有，则直接new再加上结构体的名称。

至于算法本身，直接根据大小进行合并即可，下面这个是非递归的版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    // 单调递增
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
        ListNode* head = new ListNode(0);//记住！
        ListNode* p = head;
        while(pHead1 && pHead2){
            if(pHead1->val <= pHead2->val){
                p->next = pHead1;
                pHead1 = pHead1->next;
            }
            else{
                p->next = pHead2;
                pHead2 = pHead2->next;
            }
            p = p->next;
        }
        if(pHead1) p->next = pHead1;
        if(pHead2) p->next = pHead2;
        ListNode* temp = head;
        head = head->next;
        free(temp);
        return head;
    }
};

下面这个是学习别人的递归版本。其实，递归写起来是比较短小精悍的，但关键就是要明白，结束条件是什么，怎么写递归，这也始终是我的一个短板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    // 单调递增
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
        if(pHead1 == NULL) return pHead2;
        if(pHead2 == NULL) return pHead1;
        ListNode* head = NULL;
        if(pHead1->val < pHead2->val){
            head = pHead1;
            head->next = Merge(pHead1->next, pHead2);
        }
        else{
            head = pHead2;
            head->next = Merge(pHead1, pHead2->next);
        }
        return head;
    }
}