【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;
}

---

 =========================================================================

如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容

🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏＋关注 ~🌟

=========================================================================