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

这篇具有很好参考价值的文章主要介绍了【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；如图：

【Leetcode -21.合并两个有序链表 -83.删除排序链表中的重复元素】
然后进入循环进行比较，当list1和list2都为非空，就进入循环，比较list1和list2谁小，假如list1小就把它放到tail的next，然后更新tail，更新list1；list2也同理；直到其中有一个空，就把另外一个非空的直接链接上tail的next；如图：

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

		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，如下图：

【Leetcode -21.合并两个有序链表 -83.删除排序链表中的重复元素】文章来源地址https://www.toymoban.com/news/detail-423071.html

		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;
		}

到了这里，关于【Leetcode -21.合并两个有序链表 -83.删除排序链表中的重复元素】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！