弄懂LeetCode三道题

谁借莪１个温暖的怀抱￠ 2022-11-19 01:26 203阅读 0赞

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

# 系列文章目录 #

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

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、调整奇偶数顺序
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  二、移除链表元素
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  三、反转链表
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  总结

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

# 前言 #

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

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

# 一、调整奇偶数顺序 #

[调整奇偶数顺序使奇数位于偶数前面][Link 1]

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

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。  
![在这里插入图片描述][20210414081417158.png]

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

1.  malloc创建一块空间
2.  遍历数组两遍，第一遍只存储奇数，第二遍只存储偶数。

代码如下：

int* exchange(int* nums, int numsSize, int* returnSize)
    { 
        int i=0;
        int s=0;
        int* str=(int*)malloc(sizeof(int)*numsSize);
        *returnSize=numsSize;
        for(i=0;i<numsSize;i++)
        { 
            if(nums[i]%2==1)
            { 
                str[s]=nums[i];
                s++;
            }
        }
        for(i=0;i<numsSize;i++)
        { 
            if(nums[i]%2==0)
            { 
                str[s]=nums[i];
                s++;
            }
        }
        return str;
    }

# 二、移除链表元素 #

[移除链表元素][Link 2]

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

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]![在这里插入图片描述][202104140821217.png]  
![在这里插入图片描述][20210414082141340.png]

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

1.设置哨兵结点法：不用判断第一个值是否为val  
![在这里插入图片描述][20210414082611886.png]  
代码如下：

struct ListNode* RemoveElements(struct ListNode* head, int val)
    { 
    	struct ListNode* guardhead = (struct ListNode*)malloc(sizeof(struct ListNode*));
    	guardhead->next = head;
    	struct ListNode* prev = NULL;
    	struct ListNode* cur = head;
    	while (cur)
    	{ 
    		if (cur->val == val)
    		{ 
    			struct ListNode* next = cur->next;
    			prev->next = next;
    			free(cur);
    			cur = next;
    		}
    		else
    		{ 
    			prev = cur;
    			cur = cur->next;
    		}
    	}
    	guardhead->next = head;
    	free(guardhead);
    	return head;
    }

2.不设置哨兵结点法：判断第一个值为val和第一个值不为val的情况

第一个值是val图解:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]  
第一个值不为val图解:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]

代码如下：

struct ListNode* RemoveElements(struct ListNode* head, int val)
    { 
    	struct ListNode* cur = head;
    	struct ListNode* prev = NULL;
    	while (cur)
    	{ 
    		struct ListNode* next = cur->next;
    		if (cur->val == val)
    		{ 
    			if (prev == NULL)  //第一个结点的值就是val
    			{ 
    				free(cur);
    				head = next;
    				cur = next;
    			}
    			else
    			{ 
    				prev->next = next;
    				free(cur);
    				cur = next;
    			}
    		}
    		else
    		{ 
    			prev = cur;
    			cur = cur->next;
    		}
    	}
    }

# 三、反转链表 #

[反转链表][Link 3]

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

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。  
![在这里插入图片描述][2021041408320948.png]

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

1.三指针法：定义指针1为NULL，定义指针2为head指针，定义指针3为head->next  
![在这里插入图片描述][20210414083339521.png]  
代码如下：

struct ListNode* reverseList(struct ListNode* head)
    { 
    	if (head == NULL || head->next == NULL)
    	{ 
    		return head;
    	}
    	struct ListNode* n1 = NULL, *n2 = head, *n3 = head->next;
    	while (n2)
    	{ 
    		//翻转
    		n2->next = n1;
    
    		//迭代
    		n2 = n3;
    		n1 = n2;
    		if (n3)
    		{ 
    			n3 = n3->next;
    		}
    	}
    	return n1;
    }

2.头插法:取原链表的结点依次头插到链表中  
![在这里插入图片描述][20210414083508576.png]  
代码如下：

struct ListNode* reverseList(struct ListNode* head)
    { 
    	struct ListNode* cur = head;
    	struct ListNode* newhead = NULL;
    	while (cur)
    	{ 
    		struct ListNode* next = cur->next;
    		cur->next = newhead;
    		newhead = cur;
    		cur = next;
    	}
    	return newhead;
    }

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

# 总结 #

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/07cec127f7094c2c9851ea2a71a6f4bf.png
[20210414085346438.png]: /images/20221022/dbf09f0269da4abcb036b7b77dfe5598.png
[Link 1]: https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
[20210414081417158.png]: /images/20221022/26b18b7ef0b445e3b80b1c141f10b880.png
[Link 2]: https://leetcode-cn.com/problems/remove-linked-list-elements/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210414082057742.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw,size_16,color_FFFFFF,t_70
[202104140821217.png]: /images/20221022/3b9ef2ab76144d208450e29d2c7205e4.png
[20210414082141340.png]: /images/20221022/1ec0792284a9419d954827f77486fd20.png
[20210414082611886.png]: /images/20221022/b435d9a3059243e095d38e8f1e93877e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221022/5d68f3c661d246479f54ebadbbb1aa11.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221022/dae37103ef87494e9848151e43bb165b.png
[Link 3]: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
[2021041408320948.png]: /images/20221022/d3275a49406b43c9a27b8d442aa98240.png
[20210414083339521.png]: /images/20221022/04b47beadb354d609a121ff33d8bbb14.png
[20210414083508576.png]: /images/20221022/0a11f8adcafd4c6982483fa3d38e3f9b.png
[20210414083717563.png_pic_center]: /images/20221022/79c70a93d3234db1920b4b4f0d82c42d.png