【LeetCode】【数据结构】单链表OJ常见题型（一）
👀樊梓慕：个人主页
🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》
🌝每一个不曾起舞的日子，都是对生命的辜负。
目录
前言：
【LeetCode】203.移除链表元素
【LeetCode】206.反转链表
思路一
思路二
【LeetCode】876.链表的中间结点
快慢指针法
【LeetCode】剑指Offer 22.链表中倒数第k个结点
快慢指针法
【LeetCode】21.合并两个有序链表
【LeetCode】剑指Offer Ⅱ 27.回文链表
前言：
本系列博文博主会讲解链表的经典OJ题目。
欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。
=========================================================================
GITEE相关代码：🌟fanfei_c的仓库🌟
=========================================================================
【LeetCode】203.移除链表元素
原题链接：🍏移除链表元素🍏
题目：给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。
要想删除当前元素，需要知道当前元素的位置，及前一个元素的位置，并且保存下一个元素的位置。
所以我们需要三个指针：
- 一个指针命名为cur，作用是遍历；
- 一个指针命名为prev，指向位置为cur的前一个位置，作用是删除（prev->next=cur->next）；
- 一个next指针用来保存cur的后一个位置，确保free掉cur后仍然可以找到下一元素。
代码实现：
/*
解题思路：从头节点开始进行元素删除，每删除一个元素，需要重新链接节点
*/
struct ListNode* removeElements(struct ListNode* head, int val) {if(head == NULL)return NULL;struct ListNode* cur = head;struct ListNode* prev = NULL;while(cur){//如果当前节点是需要删除的节点if(cur->val == val){//首先保存下一个节点struct ListNode* next = cur->next;//如果删除的为头节点，更新头节点//否则让当前节点的前趋节点链接next节点if(prev == NULL){head = cur->next;}else{prev->next = cur->next; }//释放当前节点，让cur指向nextfree(cur);cur = next;}else{//如果cur不是需要删除的节点，则更新prev,curprev = cur;cur = cur->next;}}return head;
}注意：考虑极端情况，如首个位置就是val的情况，作单独处理。
【LeetCode】206.反转链表
原题链接：🍏反转链表🍏
题目：给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
思路一
同样的我们需要三个指针来完成这一操作：
- 一个指针命名为cur，作用是遍历；
- 一个指针命名为prev，作用是拿到cur的前一个地址，而后改变cur->next指向prev；
- 一个指针命名为next，作用是保存cur的后一个位置，防止修改cur->next后找不到cur的后一个位置。
代码实现：
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* prev = NULL;struct ListNode* cur = head, * next = head;if (cur)// 检查cur是否为空{next = cur->next;}while (cur){// 往后走prev = cur;cur = next;if(next)// 检查next是否为空next = next->next;}return prev;
}思路二
取结点头插，完成逆置。
大家只要掌握了头插就很简单了。
代码实现：
// 取节点头插的思想完成逆置
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead = NULL;struct ListNode* cur = head;while(cur){struct ListNode* next = cur->next;//头插新节点，更新头cur->next = newhead;newhead = cur;cur = next;}return newhead;
}【LeetCode】876.链表的中间结点
原题链接：🍏链表的中间结点🍏
题目：给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
快慢指针法
若想找到中间结点，我们可以定义两个指针：
- 一个命名为slow，令slow每次走一步；
- 一个命名为fast，令fast每次走两步。
这样当fast为NULL，或fast->next为NULL时，slow恰好处于中间位置，最后返回slow即可。
代码实现：
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow=head;struct ListNode* fast=head;while(fast && fast->next)// 分别为奇数个与偶数个的判断条件{slow=slow->next;fast=fast->next->next;}return slow;
}【LeetCode】剑指Offer 22.链表中倒数第k个结点
原题链接：🍏链表中倒数第k个结点🍏
题目：输入一个链表，输出该链表中倒数第k个节点。
快慢指针法
同样需要快慢指针的方法。
令fast先走k步，slow不动，然后slow与fast同时向后走，直到fast为NULL，此时slow的位置就是倒数第k个位置。
代码实现：
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{struct ListNode* slow=head,* fast=head;while(k--){if(fast==NULL){return NULL;} fast=fast->next;}while(fast){slow=slow->next;fast=fast->next;}return slow;
}【LeetCode】21.合并两个有序链表
原题链接：🍏合并两个有序链表🍏
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：取小的尾插。
注意：极端情况的判断，如其中一个链表为空等等。
代码实现：
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(head==NULL)// 头结点直接赋值{head=tail=list1;}else// 尾插{tail->next=list1;tail=tail->next;}list1=list1->next;}else{if(head==NULL)// 头结点直接赋值{head=tail=list2;}else// 尾插{tail->next=list2;tail=tail->next;}list2=list2->next;}}if(list1)// list1有剩余{tail->next=list1;}if(list2)// list2有剩余{tail->next=list2;}return head;
}【LeetCode】剑指Offer Ⅱ 27.回文链表
原题链接：🍏回文链表🍏
题目：给定一个链表的 头节点
head，请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
思路：找到中间结点，将后半部分逆置，最后令前后两部分一一对比，如果结点的值全部相同，则为回文。
刚好我们可以利用上面实现过的函数：链表的中间结点和反转链表。
代码实现：
// 找到中间结点
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}// 反转一个单链表
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* tail = NULL;struct ListNode* cur = head, * next = head;while (next){next = cur->next;cur->next = tail;tail = cur;cur = next;}return tail;
}// 判断回文结构
bool isPalindrome(struct ListNode* head)
{struct ListNode* mid=middleNode(head);struct ListNode* newhead=reverseList(mid);while(head && newhead){if(head->val!=newhead->val){return false;}else{head=head->next;newhead=newhead->next;}}return true;
}=========================================================================
如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容
🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎
🌟~ 点赞收藏＋关注 ~🌟
=========================================================================