泰安网站建设方案书慧生活798app下载
目录
876.链表的中间结点
题目
思路
代码
206.反转链表
题目
思路
代码
21.合并两个有序链表
题目
思路
代码
203.移除链表元素
题目
思路
代码
876.链表的中间结点
876. 链表的中间结点 - 力扣（LeetCode）
https://leetcode.cn/problems/middle-of-the-linked-list/description/
题目
给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例：
思路
快慢指针法：在单链表头节点head位置创建两个指针fast和slow，两个指针通过while循环依次向后遍历，slow一次跨越一个节点slow->next，fast一次跨越两个节点fast->next->next,当fast或fast的下一节点fast->next为空时，终止循环，则此时的slow所在节点为中间节点。
代码
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}206.反转链表
206. 反转链表 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-linked-list/description/
题目
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
示例：
思路
依次断开原链表的第一个节点，用头插的方式插入新链表，注意注意要保存好cur的下一节点next。
代码
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;
}21.合并两个有序链表
21. 合并两个有序链表 - 力扣（LeetCode）https://leetcode.cn/problems/merge-two-sorted-lists/description/
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
思路
创建一个新的结构体指针head作为合成的新链表，
创建两个指针，指向两个链表，将两个有序链表从头节点开始，依次进行比较，取较小的尾插到新的链表，通过while循环直到其中一个链表为空，不为空的链表直接尾插到新链表即可。
图示如下👇
在插入第一个节点前，我们也可以选择放一个哨兵位在头节点前面（哨兵位不算链表节点），这样就减少了第一次尾插时对tail是否为空的判断，代码更加简洁。
代码
不带哨兵位
带哨兵位
203.移除链表元素
203. 移除链表元素 - 力扣（LeetCode）https://leetcode.cn/problems/remove-linked-list-elements/description/
题目
给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。
示例：
思路
这道题可以用双指针法，两个指针逐渐向后遍历，当遇到满足cur->val=val的节点时，（满足cur==hand时用头删的方法）cur到下一节点保存下一节点，同时删除满足条件的节点，每趟循环cur会赋给prev，cur再到下一节点，当cur遍历链表完为NULL的时候，prev刚好在最后一个节点，prev->next为链表结尾赋NULL。
代码
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* prev=NULL,* cur=head;while(cur){if(cur->val==val){if(cur==head){head=cur->next;free(cur);cur=head;}else{prev->next=cur->next;free(cur);cur=prev->next;}}else{prev=cur;cur=cur->next;}}return head;}