【Leetcode -21.合并两个有序链表 -83.删除排序链表中的重复元素】

简介: 【Leetcode -21.合并两个有序链表 -83.删除排序链表中的重复元素】

Leetcode-21.合并两个有序链表

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

示例 1:

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

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

示例 2:

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

输出:[]

示例 3:

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

输出:[0]

我们的思路是,先定义两个结构体的空指针head和tail,然后先第一次比较list1和list2,谁小就把它的头节点赋给head和tail,然后更新list1或者list2;如图:

然后进入循环进行比较,当list1和list2都为非空,就进入循环,比较list1和list2谁小,假如list1小就把它放到tail的next,然后更新tail,更新list1;list2也同理;直到其中有一个空,就把另外一个非空的直接链接上tail的next;如图:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
    {
        //list1和list2其中一个链表为空,返回另外一个
        if (list1 == NULL)
        {
            return list2;
        }
        else if (list2 == NULL)
        {
            return list1;
        }
        //定义两个结构体的指针
        struct ListNode* head = NULL;
        struct ListNode* tail = NULL;
        //首先第一次比较,比较list1和list2谁小,就把这个头节点赋给head和tail
        if (list1->val < list2->val)
        {
            head = tail = list1;
            list1 = list1->next;
        }
        else
        {
            head = tail = list2;
            list2 = list2->next;
        }
        //当list1和list2都不为空,循环继续
        while (list1 && list2)
        {
            //开始逐一比较,假如list1小就把它放到tail的next,然后更新tail,更新list1
            if (list1->val < list2->val)
            {
                tail->next = list1;
                tail = tail->next;
                list1 = list1->next;
            }
            //list2小或者等于就把它放到tail的next,然后更新tail,更新list2
            else
            {
                tail->next = list2;
                tail = tail->next;
                list2 = list2->next;
            }
        }
        //直到其中有一个空,就把另外一个非空的直接链接上tail的next
        if (list1 == NULL)
        {
            tail->next = list2;
        }
        else
        {
            tail->next = list1;
        }
        return head;
    }

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

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

示例 1:

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

输出:[1, 2]

示例 2:

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

输出:[1, 2, 3]

我们的思路是,定义两个指针,寻找重复的元素,当两个指针指向的元素相等,就将第一个先出现的指向第二次出现的next,如下图:

struct ListNode* deleteDuplicates(struct ListNode* head)
    {
        //head为空指针,返回空指针
        if (head == NULL)
        {
            return NULL;
        }
        //定义cur和del指针,cur从头开始,del从cur的next开始
        struct ListNode* cur = head, * del = head->next;
        //当del不为空
        while (del)
        {
            //当cur的val等于del的val,即出现了重复元素
            if (cur->val == del->val)
            {
                //将del的next赋给cur的next,即cur指向了del的next
                cur->next = del->next;
                //更新del
                del = del->next;
            }
            //当cur的val不等于del的val,即不是重复元素
            else
            {
                //更新cur和del
                cur = cur->next;
                del = del->next;
            }
        }
        return head;
    }
目录
相关文章
|
2月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
38 1
|
2月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
38 0
|
2月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
56 0
|
2月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
34 0
|
2月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
33 0
|
2月前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
33 0
|
4月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
4月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
6月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表