【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月前
|
Python
【Leetcode刷题Python】21. 合并两个有序链表
介绍了几种不同的方法来合并多个已排序的链表,包括暴力求解、使用小顶堆以及分而治之策略。
34 2
|
2月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
2月前
|
算法
LeetCode第21题合并两个有序链表
该文章介绍了 LeetCode 第 21 题合并两个有序链表的解法,通过创建新链表,依次比较两个链表的头节点值,将较小的值插入新链表,直至其中一个链表遍历完,再将另一个链表剩余部分接到新链表后面,实现合并。
LeetCode第21题合并两个有序链表
|
2月前
|
算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
|
3月前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
35 8
【数据结构OJ题】合并两个有序链表
|
2月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
20 0
|
3月前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
33 2
|
3月前
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
25 0
|
3月前
链表6(法二好理解)------ 7-6 sdut-C语言实验-有序链表的归并分数 20
链表6(法二好理解)------ 7-6 sdut-C语言实验-有序链表的归并分数 20
17 0
|
3月前
sdut 链表6-------7-6 sdut-C语言实验-有序链表的归并
sdut 链表6-------7-6 sdut-C语言实验-有序链表的归并
16 0