数据结构（c语言实现）|＜数据结构＞刷题笔记——链表篇（一）（有动图详解） c语言|数据结构|后端|刷题

文章目录

1. 移除链表元素
- 解题思路：
- 链接：
2. 反转链表
- 解题思路：
- 链接：
3. 合并两个有序链表
- 解题思路：
- 链接：

1. 移除链表元素给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

示例 1：

文章图片
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

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

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
解题思路：

文章图片

以上情况你用两个指针也行，但要小心顺序问题。
还要小心第一个元素就要删除的情况，那样的话就把head往后移

struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* prev = NULL; struct ListNode* cur = head; while(cur) { if(cur->val == val) { struct ListNode* next = cur->next; if(prev == NULL)//如果第一个元素就要删除，就把head往后移 { free(cur); head = next; cur = next; } else { prev->next = next; free(cur); cur = next; } } else { prev = cur; cur = cur->next; } } return head; }

链接： 【数据结构（c语言实现）|＜数据结构＞刷题笔记——链表篇（一）（有动图详解）】力扣203. 移除链表元素
2. 反转链表给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

文章图片

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

文章图片

输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
解题思路：方法一：反转指向

文章图片

//方法1 ?struct ListNode* reverseList(struct ListNode* head){ if(head == NULL)return NULL; struct ListNode* n1,*n2,*n3; n1 = NULL; n2 = head; n3 = head->next; while(n2) { n2->next = n1; n1 = n2; n2 = n3; if(n3) n3 = n3->next; //为了防止n3为空的情况 } return n1; }

方法二：创建新链表头插

文章图片

//方法二 struct ListNode* reverseList(struct ListNode* head){ struct ListNode* newhead = NULL, *cur = head, *next; while(cur) { next = cur->next; cur->next = newhead; newhead = cur; cur = next; } return newhead; }

链接：力扣206. 反转链表
3. 合并两个有序链表将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

文章图片

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

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

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

提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列
解题思路：创建一个新链表，按从小到大顺序把数据重新尾插到新链表中（tail指针为了简化找尾过程）

文章图片

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //为了防止只有一个链表有数据 if(list1 == NULL) return list2; if(list2 == NULL) return list1; struct ListNode* head = NULL, *tail = NULL; while(list1 && list2) { if(list1->val < list2->val) { if(tail == NULL) { head = tail = list1; } else { tail->next = list1; tail = list1; } list1 = list1->next; } else { if(tail == NULL) { head = tail = list2; } else { tail->next = list2; tail = list2; } list2 = list2->next; } } if(list1 != NULL) { tail->next = list1; } if(list2 != NULL) { tail->next = list2; } return head; }

这道题还有一种更简便的写法，这种写法要引出带头节点的单链表的概念。顾名思义，带头节点的单链表有一个哨兵卫的头结点，但这个节点不存储有效数据。那么它有什么意义吗？它能够简化过程，让第一次插入和非第一次插入合并起来，看看以下的代码你就理解它的方便之处了。tail==NULL的情况不用单独讨论了。

文章图片

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* head = NULL, *tail = NULL; //带头节点 head = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); head->next = NULL; while(list1 && list2) { if(list1->val < list2->val) { tail->next = list1; tail = list1; list1 = list1->next; } else { tail->next = list2; tail = list2; list2 = list2->next; } } if(list1 != NULL) { tail->next = list1; } if(list2 != NULL) { tail->next = list2; } struct ListNode* list = head->next; //head不存数据，要返回head的下一个 free(head); return list; }

链接：力扣21. 合并两个有序链表