题目链接

https://leetcode-cn.com/problems/merge-two-sorted-lists/description/

题目分析

• 两个链表已排序
• 新链表应该是两个链表拼接起来的，而非new出来的
• 链表中头结点的val应该是有意义的

题解一：迭代

思路

1. 先new一个无意义的头结点，方便建立新链表
2. 同时遍历两个链表并拼接至新链表，每取一个结点就更新其所在链表的指针和新链表指针，直至两个链表中的某一个遍历结束
3. 将未遍历完的链表拼接至新链表
4. delete无意义的头结点，释放内存，返回其next

代码

// Problem: LeetCode 21
// URL: https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
// Tags: Linked List Recursion Iteration
// Difficulty: Easy

#include <iostream>
using namespace std;

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) {
        // 定义头结点，方便建立新链表
        ListNode *head = new ListNode(-1);
        // 遍历链表用的指针
        ListNode *l3 = head;
        // 同时遍历两个链表并拼接值较小的结点到新链表中，同步更新链表指针，直至某个链表遍历结束
        while (l1 != nullptr && l2 != nullptr){
            if (l1->val < l2->val){
                l3->next = l1;
                l1 = l1->next;
            }else{
                l3->next = l2;
                l2 = l2->next;
            }
            l3 = l3->next;
        }
        // 将未遍历完的链表拼接至新链表
        if(l1!=nullptr){
            l3->next = l1;
        }
        if (l2 != nullptr){
            l3->next = l2;
        }

        // 释放无意义头结点并返回其next
        l3 = head->next;
        delete head;
        return l3;
    }
};

int main()
{
    // system("pause");
    return 0;
}

题解二：递归

再思递归

昨天也做了一个递归题，今天这道题也可以用递归，我又有了一些关于递归的想法：

• 递归表达式
  • 其实就是函数，要求明确几点：输入、输出、功能、拼接公式，有时候还需要知道函数运行对各个变量的影响（比如昨天那道题从代码二修改至代码三）
• 递归出口（也包括边界）
  • 一定要最小化
  • 要求能够处理递归表达式的已知情况，即输入取特定值（因题目而不同）时的情况

思路

• 递归表达式

  • 输入：两个链表的头指针
  • 输出：两个链表拼接后的头指针
  • 功能：将两个链表拼接

• 递归出口

  链表指针为null时。如果出口是next为null，这个出口并不是最小化的

递归函数实现的功能和思路为：

递归函数拿到了两个链表A和B，取出两个链表中值较小的那个头结点N，然后通过递归拼接剩下的两个链表返回M，然后手动拼接N和M。

思路模拟：

假设是链表A的头结点N的值比较小，那我取出其头结点N后形成一个新的链表A1（不包括头结点），然后通过递归拼接A1和B返回M，然后手工拼接N和M（即N->next=M;）。

代码

// Problem: LeetCode 21
// URL: https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
// Tags: Linked List Recursion Iteration
// Difficulty: Easy

#include <iostream>
using namespace std;

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) {
        // 边界和递归出口
        if(nullptr==l1){return l2;}
        if(nullptr==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;
        }
    }
};

int main()
{
    // system("pause");
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!