🌺21. 合并两个有序链表

🍁题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]

输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []

输出：[]

示例 3：

输入：l1 = [], l2 = [0]

输出：[0]

提示：

   两个链表的节点数目范围是 [0, 50]

   -100 <= Node.val <= 100

   l1 和 l2 均按 非递减顺序 排列

🍁基础框架

• C++ 版本给出的基础框架代码如下：

/**
 * Definition for singly-linked list.
 * 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* list1, ListNode* list2) {
    }
};

🍁详细思路

🍀思路一【迭代】

当l1和l2都不是空链表时，判断l1和l2的头结点的大小，将较小的结点连在答案后面，将该结点对应链表后移一位。

💬 代码演示

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* Head = new ListNode(-1);
        ListNode* p = Head;
        while (l1 != nullptr && l2 != nullptr) 
        {
            if (l1->val < l2->val) 
            {
                p->next = l1;
                l1 = l1->next;
            } 
            else 
            {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        p->next = l1 == nullptr ? l2 : l1;
        return Head->next;
    }
};

🍉知识点

p->next = l1 == nullptr ? l2 : l1;        //将非空链表接在合并链表的后面

🍀思路二【递归】

递归三部曲

1. 递归结束条件，
2. 找到函数的等价关系式
3. 调用函数

（1）当l1为空时，返回l2。当l2为空时，返回l1.

（2）比较看看哪个结点小，决定下一次递归的参数

（3）调用函数

💬 代码演示

/**
 * Definition for singly-linked list.
 * 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 (l1 == nullptr)
         {
            return l2;
        } 
        else if (l2 == nullptr) 
        {
            return l1;
        } 
        else if (l1->val < l2->val) 
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } 
        else 
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

🍉知识点

递归三部曲的思想

🌺83. 删除排序链表中的重复元素

🍁题目描述

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]

输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]

输出：[1,2,3]

提示：

   链表中节点数目在范围 [0, 300] 内

   -100 <= Node.val <= 100

   题目数据保证链表已经按升序 排列

🍁基础框架

• C++ 版本给出的基础框架代码如下：

/**
 * Definition for singly-linked list.
 * 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* deleteDuplicates(ListNode* head) {
    }
};

🍁详细思路

🍀思路一【遍历】

从头到尾遍历，是重复元素就删除，不是则判断下一结点

💬 代码演示

/**
 * Definition for singly-linked list.
 * 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* deleteDuplicates(ListNode* head) {
        if(head==NULL)
        {
            return head;
        }
        ListNode* cur=head;
        while(cur->next)
        {
            if(cur->val == cur->next->val)
            {
                cur->next = cur->next->next;
            }
            else
            {
                cur = cur->next;
            }
        }
        return head;
    }
};

本人不才，如有错误，欢迎各位大佬在评论区指正。有帮助的话还请【关注➕点赞➕收藏】，不行的话我再努努力💪💪💪