Leetcode-21.合并兩個(gè)有序鏈表

題目：將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例 1：
輸入：l1 = [1, 2, 4], l2 = [1, 3, 4]
輸出：[1, 1, 2, 3, 4, 4]

示例 2：
輸入：l1 = [], l2 = []
輸出：[]

示例 3：
輸入：l1 = [], l2 = [0]
輸出：[0]

我們的思路是，先定義兩個(gè)結(jié)構(gòu)體的空指針head和tail，然后先第一次比較list1和list2，誰小就把它的頭節(jié)點(diǎn)賦給head和tail，然后更新list1或者list2；如圖：

然后進(jìn)入循環(huán)進(jìn)行比較，當(dāng)list1和list2都為非空，就進(jìn)入循環(huán)，比較list1和list2誰小，假如list1小就把它放到tail的next，然后更新tail，更新list1；list2也同理；直到其中有一個(gè)空，就把另外一個(gè)非空的直接鏈接上tail的next；如圖：

		struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
		{
		    //list1和list2其中一個(gè)鏈表為空，返回另外一個(gè)
		    if (list1 == NULL)
		    {
		        return list2;
		    }
		
		    else if (list2 == NULL)
		    {
		        return list1;
		    }
		
		    //定義兩個(gè)結(jié)構(gòu)體的指針
		    struct ListNode* head = NULL;
		    struct ListNode* tail = NULL;
		
		    //首先第一次比較，比較list1和list2誰小，就把這個(gè)頭節(jié)點(diǎn)賦給head和tail
		    if (list1->val < list2->val)
		    {
		        head = tail = list1;
		        list1 = list1->next;
		    }
		
		    else
		    {
		        head = tail = list2;
		        list2 = list2->next;
		    }
		
		    //當(dāng)list1和list2都不為空，循環(huán)繼續(xù)
		    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;
		        }
		    }
		
		    //直到其中有一個(gè)空，就把另外一個(gè)非空的直接鏈接上tail的next
		    if (list1 == NULL)
		    {
		        tail->next = list2;
		    }
		    else
		    {
		        tail->next = list1;
		    }
		
		    return head;
		}

Leetcode-83.刪除排序鏈表中的重復(fù)元素

題目：給定一個(gè)已排序的鏈表的頭 head ， 刪除所有重復(fù)的元素，使每個(gè)元素只出現(xiàn)一次 。返回已排序的鏈表 。

示例 1：
輸入：head = [1, 1, 2]
輸出：[1, 2]

示例 2：
輸入：head = [1, 1, 2, 3, 3]
輸出：[1, 2, 3]

我們的思路是，定義兩個(gè)指針，尋找重復(fù)的元素，當(dāng)兩個(gè)指針指向的元素相等，就將第一個(gè)先出現(xiàn)的指向第二次出現(xiàn)的next，如下圖：

文章來源地址http://www.zghlxwxcb.cn/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;
		
		    //當(dāng)del不為空
		    while (del)
		    {
		        //當(dāng)cur的val等于del的val，即出現(xiàn)了重復(fù)元素
		        if (cur->val == del->val)
		        {
		            //將del的next賦給cur的next，即cur指向了del的next
		            cur->next = del->next;
		
		            //更新del
		            del = del->next;
		        }
		
		        //當(dāng)cur的val不等于del的val，即不是重復(fù)元素
		        else
		        {
		            //更新cur和del
		            cur = cur->next;
		            del = del->next;
		        }
		    }
		    return head;
		}

到了這里，關(guān)于【Leetcode -21.合并兩個(gè)有序鏈表 -83.刪除排序鏈表中的重復(fù)元素】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！