学会链表中LeetCode三道题

╰半夏微凉° 2023-01-13 05:46 120阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、链表的中间结点
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  二、链表的倒数第k个结点
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  三、合并两个排序的链表
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  总结

--------------------

# 前言 #

--------------------

![在这里插入图片描述][20210416100153995.png]

# 一、链表的中间结点 #

[链表的中间结点][Link 1]

#### 1.题目描述 ####

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。  
![在这里插入图片描述][20210416100335839.png]  
![在这里插入图片描述][20210416100448325.png]

#### 2.解题思路 ####

可以采用快慢指针方法:设置两指针，慢指针速度一次一个结点，快指针一次两个结点。这种方法只遍历了一次链表  
![在这里插入图片描述][20210416100840673.png]

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<string.h>
    struct ListNode
    { 
    	int val;
    	struct ListNode* next;
    };
    //快慢指针方法
    struct ListNode* middleNode(struct ListNode* head)
    { 
    	struct ListNode* fast = head, *slow = head;
    	while (fast&&fast->next)
    	{ 
    		slow = slow->next;
    		fast = fast->next->next;
    	}
    	return slow;
    }

# 二、链表的倒数第k个结点 #

#### 1.题目描述 ####

[链表中倒数第k个结点][k]

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。  
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。  
![在这里插入图片描述][20210416101230937.png]

#### 2.解题思路 ####

同样采用快慢指针方法，让快指针先走k步，结束后快慢指针再次同时出发，快指针结束时慢指针就是走的结果。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]  
代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    struct ListNode
    { 
    	int val;
    	struct ListNode* next;
    };
    struct ListNode* getKthFromEnd(struct ListNode* head, int k)
    { 
    	struct ListNode* fast = head, *slow = head;
    	while (k--)
    	{ 
    		if (fast == NULL)
    		{ 
    			return NULL;
    		}
    		fast = fast->next;
    	}
    	while (fast)
    	{ 
    		fast = fast->next;
    		slow = slow->next;
    	}
    	return slow;
    }

# 三、合并两个排序的链表 #

#### 1.题目描述 ####

[合并两个有序链表][Link 2]

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20210416102146162.png]  
![在这里插入图片描述][20210416102154432.png]

#### 2.解题思路 ####

第一种方法：不带哨兵位  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]

代码如下：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
    { 
    	//判断哪个链表为空，然后返回另一个链表
    	if (l1==NULL)
    	{ 
    		return l2;
    	}
    	if (l2 == NULL)
    	{ 
    		return l1;
    	}
    	struct ListNode* head = NULL, *tail = NULL;
    	//先去两个链表中小的作为第一个结点
    	if (l1->next < l2->next)
    	{ 
    		head = tail = l1;
    		l1 = l1->next;
    	}
    	else
    	{ 
    		head = tail = l2;
    		l2 = l2->next;
    	}
    	//去链表中其他结点相比较尾插到第一个结点后面
    	while (l1&&l2)
    	{ 
    		if (l1->val < l2->val)
    		{ 
    			tail->next = l1;
    			l1 = l1->next;
    		}
    		else
    		{ 
    			tail->next = l2;
    			l2 = l2->next;
    		}
    		tail = tail->next;
    	}
    	//判断谁还有结束且后面还有结点，直接链接到尾结点上去
    	if (l1)
    	{ 
    		tail->next = l1;
    	}
    	if (l2)
    	{ 
    		tail->next = l2;
    	}
    	return head;
    }

第二种方法：带哨兵位  
代码如下：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
    { 
    	struct ListNode* head = NULL, *tail = NULL;
    	//创建一个哨兵位的头结点
    	head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    	tail->next = NULL;
    	while (l1&&l2)
    	{ 
    		if (l1->val < l2->val)
    		{ 
    			tail->next = l1;
    			l1 = l1->next;
    		}
    		else
    		{ 
    			tail->next = l2;
    			l2 = l2->next;
    		}
    		tail = tail->next;
    	}
    	if (l1)
    	{ 
    		tail->next = l1;
    	}
    	if (l2)
    	{ 
    		tail->next = l2;
    	}
    	struct ListNode* node = head;
    	head = head->next;
    	free(node);
    	return head;
    }

--------------------

# 总结 #

本文仅仅简单介绍了链表常见的三题，这些题目我们以后可能会遇到，我们务必掌握。另外，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。

![在这里插入图片描述][20210416102731360.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/af4431204dd24cec8d76503286687ea1.png
[20210416100153995.png]: /images/20221022/b9c11f118dd344bab6373f526c6b3c6e.png
[Link 1]: https://leetcode-cn.com/problems/middle-of-the-linked-list/
[20210416100335839.png]: /images/20221022/4ad6a5416da04951827bb7b2bada82e8.png
[20210416100448325.png]: /images/20221022/65d2066162c542f8ba2fd54a62168955.png
[20210416100840673.png]: /images/20221022/6bf4681f4db84fccb10fa48780d272d1.png
[k]: https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
[20210416101230937.png]: /images/20221022/c0b6f57bafde49d29856c9fe9b27af64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221022/7f691e0288094915aecf3ce2edf04887.png
[Link 2]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221022/0c9ca867b85f4408bd45aaa62a9c20e1.png
[20210416102146162.png]: /images/20221022/979d872c6af8459aa8b1d5891f0acd98.png
[20210416102154432.png]: /images/20221022/35ba7cd9a7c44846ba0e8f0837ddebc7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221022/0787b7961d8544fda4e9dc3085f41a30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221022/5ef0522ed38745adbd9b7a17b4b1818c.png
[20210416102731360.png_pic_center]: /images/20221022/e5ba84b867934d70ba1b80a7f46db9ed.png